比赛的时候忘了注册了不给比…… 这下记住==赛前需要先注册了==

CF: Cost of the Array

Problem - B - Codeforces

看的时候一开始以为是找最大成本，结果其实是最小成本。这就简单了，分两类讨论：

情况1

如果n=k，说明分子数组的分法是固定的，比如 a=[1,1,2,2,3,3,4,4,5,5]，a.size()=10，然后 k=10，那么就是每个子数组一个元素：[1], [1], [2], [2]…… 这样 b=[1,2,3,4,5,0]。既然分发是固定的，直接遍历 a的偶数项然后看它对应到 b里元素等不等于它在 b里的位置（也就是下标+1）。代码如下：

if (k == n) {
        for (int i = 1; i < n; i += 2) {
            int index_in_b = (i + 1) / 2;
            if (a[i] != index_in_b) {
                cout << index_in_b << endl;
                return;
            }
        }
        cout << k / 2 + 1 << endl;
    }

情况2：

如果n>k，说明可以有手动操作的空间。那么我们贪心的想：b的得一个元素最好不要是1，这样cost=1。就在 a[1……n-k+1]这个区间里看有没有不是1的值。一种情况是：a=[?, 1, 1, 1, 1, 1, ?, ?, ? ...] 全是1，那么答案就是2。因为 b=[1, 1, ....]。另外一种情况是有不是1的值：a[?, 1, 1, 7, ?, ?, ? ...] 那么就可以把 [?,1,1]分一起，然后 [7]，这样 b=[7,?,?...]。那么答案就是1。

else {
        for (int i = 1; i <= n - k + 1; i++) {
            if (a[i] != 1) {
                cout << 1 << endl;
                return;
            }
        }
        cout << 2 << endl;
    }

代码

/*
 * Created by: Chixiyu
 * Date: 2025-02-10
 */
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &it : a)
        cin >> it;
    if (k == n) {
        for (int i = 1; i < n; i += 2) {
            int index_in_b = (i + 1) / 2;
            if (a[i] != index_in_b) {
                cout << index_in_b << endl;
                return;
            }
        }
        cout << k / 2 + 1 << endl;
    } else {
        for (int i = 1; i <= n - k + 1; i++) {
            if (a[i] != 1) {
                cout << 1 << endl;
                return;
            }
        }
        cout << 2 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}