研发C题的思路分享

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k, mini = 10001, maxi = 0;
    cin >> n >> k;
    vector<int> h(10001);

    // 输入数据，统计每个数字个数，以及最大最小值
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin >> tmp;
        mini = min(mini, tmp);
        maxi = max(maxi, tmp);
        h[tmp]++;
    }

    int ans = 2e9;
    // 遍历最后相同的k个数是多少
    for (int target = mini; target <= maxi; ++target) {
        // 如果target已经有k个，输出0结束，否则得到还需要多少个。
        int rem = k - h[target];
        if (rem <= 0) {
            cout << 0;
            return 0;
        }

        // 求出把比target小的数字全部抬到target-1所需要的代价
        // 求出把比target大的数字全部降到target+1所需要的代价
        // 这两个循环可以通过做h[y]和h[y]*y两个前缀和的方式降低复杂度。
        int left_cost = 0, right_cost = 0;
        int left_total = 0, right_total = 0;
        for (int y = mini; y <= target - 1; ++y) {
            left_total += h[y];
            left_cost += h[y] * (target - y - 1);
        }
        for (int y = target + 1; y <= maxi; ++y) {
            right_total += h[y];
            right_cost += h[y] * (y - target - 1);
        }

        // 如果小的数字数目足够，尝试把小数字全部抬到target-1后再把其中rem个抬到target
        if (left_total >= rem) {
            ans = min(ans, left_cost + rem);
        }
        // 如果大的数字数目足够，尝试把大数字全部降到target+1后再把其中rem个降到target
        if (right_total >= rem) {
            ans = min(ans, right_cost + rem);
        }
        // 如果都不够，则同时将小数字抬到target-1且大数字降到target+1，然后将其中rem个升或降到target
        if (left_total < rem && right_total < rem) {
            ans = min(ans, left_cost + right_cost + rem);
        }
    }
    cout << ans;
    return 0;
}