原题链接
https://www.acwing.com/problem/content/3996/
题目描述
有 n 堆石子，石子数量分别为 a1,a2,…,an。 现在，需要你通过取石子操作，使得所有堆石子的数量都相同。 一轮取石子操作的具体流程为： 设定一个石子数量上限 h。 检查每堆石子，对于石子数量大于 h 的石子堆，取出多余石子，使其石子数量等于 h。 要求，在一轮取石子操作中取走的石子数量不得超过 k。 请计算并输出为了使得所有堆石子的数量都相同，最少需要进行多少轮取石子操作。 输入格式 第一行包含两个整数 n,k。 第二行包含 n 个整数 a1,a2,…,an。 输出格式 一个整数，表示所需的最少取石子操作轮次。 数据范围 前六个测试点满足， 1≤n≤k≤10。 所有测试点满足，1≤n≤2×105，n≤k≤109，1≤ai≤2×105。 输入样例1： 5 5 3 1 2 2 4 输出样例1： 2 输入样例2： 4 5 2 3 4 5 输出样例2： 2
ac代码
#include#include #include #include using namespace std; int n, k, l, r, ans; int ss[200010], s[200010]; int main(){ cin >> n >> k; for (int i = 1, x ; i <= n ; i ++){ scanf("%d", &x); s[x] ++; ss[x] += x; r = max(r, x); } l = r; for (int i = 1 ; i <= r ; i ++) s[i] += s[i - 1], ss[i] += ss[i - 1]; // 这里的 l 即为 h，表示我们每次操作的下界，我们每次操作都会把比 l 大的数变为l // 而 r 即为当前序列中最大的数（也就是上一次操作的 h，对于比 h 大的数我们不需修改，直接忽略） while(s[l - 1] != 0){ //当没有比 l 更小的数的时候说明模拟结束 while(ss[r] - ss[l] - (s[r] - s[l]) * l <= k && s[l] != 0) l --; // 注意这里s[l] != 0，如果 l + 1 已经是最小的数就不用再减小l了 l ++; ans ++; ss[l] += (s[r] - s[l]) * l; s[l] += (s[r] - s[l]); // 更新 s[l] 和 ss[l] r = l; } cout << ans; } 作者：Randolph 链接：https://www.acwing.com/solution/content/60381/ 来源：AcWing
一位大佬的题解，非常巧妙的方法。
前缀和 + 巧妙暴力模拟QwQ
自己在比赛时创造的一种独特前缀和做法QwQ，虽然说这题可能有更简洁的做法，但是我觉得这个前缀和的新技巧还是挺有趣的
理解题意，可以思考这样一种暴力模拟的思路：
刚开始把 h 设为最大的数，然后将所有比 h 大的数都减去 h 得到的总和与 k 比较，如果不超过 k ，则可以将 h - -，贪心找到使总和不超过 k 的最小的 h ，然后将比 h 大的数都变为 h ，重复模拟该过程直到所有数相同（即 h 取到最小的数）
关键的难点就在于如何快速求出这个总和，我们灵机一动不难发现，用前缀和可以解决：
s[i] 表示数字 i 出现的次数，再开一个 ss[i] 数组，数字 i 每出现一次，ss[i] 就加上 i ，然后对 s[i] 和 ss[i] 数组求一遍前缀和。
这样一来，用ss[r] - ss[l]可以求出在 (l, r] 区间内所有数的和，用 s[r] - s[l] 可以求出在 (l, r] 区间内所有数的个数，
那么你就会惊奇地发现，我们所要求的总和即为 ss[r] - ss[l] - (s[r] - s[l]) * l
另外，暴力模拟中有一步操作是将比 h 大的数都变为 h，我们没必要真的一个一个去修改比 h 大的数，因为他们对 h 之前的前缀和并不会产生影响，我们只需对 s[h] 和 ss[h] 进行更新即可
从这我学到了：先通过暴力方法梳理清楚思路，再对每一步思考可行的优化，不断提高解法的效率，无疑是一种不错的解题策略
先考虑暴力怎么做，再思考怎么通过算法来优化
另外在做题时，发现一些问题。
int n, k, l, r, ans;
int ss[200010], s[200010]
定义变量时，如果都是局部变量，会超时。
如果单独定义数组为全局变量时，会Segmentation Fault；
至于为什么，我还不清楚。
不过以后写题定义变量最好是全局部，或者全全局，毕竟是一锤子买卖。
