研发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)).