研发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;
}

思路的关键点在于,如果试图将任意一个大于target的数降到target,必须经过target+1,而想把target+1降到target,必须保证target+1是最大,那么就必须把所有大于target的都先搞到target+1才行。
内部两个循环用前缀和优化以后时间复杂度是O(maxi-mini)(不包括输入的O(n)).

全部评论
楼主思路很直白,我也搞了一个思路,不确定对错,请指正 https://ac.nowcoder.com/discuss/420579
点赞 回复
分享
发布于 2020-04-30 08:48

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务