C、序列最小化

因为是一个全排列数组，最终一定全部换成1，那么这个过程中替换1以外的数字都是多花功夫，记录全部换成1最少的步骤。

方法一：比较朴素的方法记录到1出现的位置，枚举最开始更新1的区间，再计算起始区间左边+右边需要的次数，更新答案取最小值即可。
这种方法有一个好处，就是如果你采取这个方法，不会给自己踩坑里去，算出来一定是正确的。
下面给出我的参考代码，注意两点就行了，起始左右区间不要越界，每次总数减少k-1个

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main() {
    int n = read(), k = read();
    int tag = -1;
    for (int i = 1; i <= n; ++i) {
        int tmp = read();
        if (tmp == 1)    tag = i;
    }
    int ans = 0x3f3f3f3f;
    for (int l = max(1, tag - k + 1); l <= tag; ++l) { //注意左右区间别越界了
        int r = l + k - 1;
        int a1 = ceil(1.0 * (l - 1) / (k - 1));
        int a2 = ceil(1.0 * (n - r) / (k - 1));
        ans = min(ans, a1 + a2 + 1);
    }
    printf("%d\n", ans);
    return 0;
}

方法二：是我昨天想到的办法，昨天我想的比较浅显，没有给自己掉牛角尖里面去。
给我n个数，每次合并k个数再放回之前的位置去，重复这个操作直到数目小于等于1。
可以得到关系式： $图片说明$
得到我们要求的 $图片说明$ 。
不过这个我昨天举得栗子比较简单，今天突然想到一个反例，我是吧这k个数合并成一个数，再放回去，本来按照这个题目意思，这k个数看成一个数容易出BUG。
比如 5 4 1 3 2，我本来想的是4 1 3第一次合并写出1。
5 1 2合并，得到答案2。
那么很显然这个答案是错误的，我单纯的看成1个数其实是一个集合，不过这个方法为什么没有WA呢。
我想到一个可能解释的理由，这种方法，可能产生歧义的地方就在于你选取起始区间合并，再分别向左和向右展开，最后剩余最左边剩余元素和最右边剩余元素小于等于k-1，这个时候你单纯以为直接和左边中间右边合并就是错误的，既然是这样的情况的话我们有没有别的方法去改变呢，没错回到方法一，更换起始区间，既然两边剩余元素之和小于等于k-1，那么我就可以选择吧一边调整到没有剩余，那么对应的另一边，也可以在一次之内吧剩余元素合并完成！！是不是很有道理，当然本菜鸡竟然想这个地方想了一早上。 +_+
贴上我昨天的代码

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) int tmp = read();
    int ans = ceil(1.0 * (n - 1) / (m - 1));
    printf("%d\n", ans);
    return 0;
}

牛客算法周周练5

C、序列最小化