题目内容

原题链接

给定一个长度为 $n$ 的数组 $a$ ，每次操作可以选择一个数 $x$ ，将所有大于 $x$ 的数都下降为 $x$ ，一次操作的下降总代价为 $s$ ，要求 $s\le k$ ，问需要多少次操作使得数组 $a$ 的所有数都相同。

数据范围

• $1\le n\le 2\cdot 10^5$
• $n\le k\le 10^9$
• $1\le a_i\le 2\cdot 10^5$

题解

朴素做法

首先使得所有数都相同，则使得所有值都成为 $min(a)$ 。

所以考虑怎么将所有数都变成 $min(a)$ 。

先对 $a$ 排序，然后从最大的数开始依次将前面大的数往小了降。

从大的值开始往下依次枚举，看每次的 $k$ 可以将前面多少数统一下降为一个数。

因为值域很小，所以可以直接枚举值域，这样的时间复杂度是 $O(max(a)+n)$

优化做法

如果值域很大，是否有与值域无关的做法。

其实这种题本身就应该值域无关，考虑当前最大的数为 $cur$ ，有 $cnt$ 个值为 $cur$ 的数，下一步变成一个大于 $a[j]$ 的最小的数 $nxt$。

那么就有 $(cur-nxt)\times cnt$ 的代价将所有的 $cur$ 变成 $nxt$ 。

所有相邻元素如果差距过大，考虑将统一下降的部分额外操作出来，保证我们每次循环的开始都是先用一个操作将整体的数做下降。

这样可以保证一次遍历就可以将所有元素都变成 $min(a)$ 。

时间复杂度：$O(n\log n)$

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;void solve() {int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; ++i) cin >> a[i];sort(a.begin(), a.end(), greater<>());if (a.back() == a.front()) {cout << "0\n";return;}// 一次 k 能够支撑多少元素下降ll ans = 0;ll pre = 0;ll cnt = 0;ll cur = -1;for (int i = 0; i < n; ++i) {ll s = k;// 第一个 s 到某个 a[j - 1]int j = i;while (j < n && pre - cnt * a[j] <= s) {cur = a[j];pre += a[j];cnt += 1;j += 1;}// pre 肯定是一个统一的值if (j > i) {s -= pre - cnt * a[j - 1];// 然后把剩下部分给整了ll dec = s / cnt;cur = a[j - 1] - dec;pre = cur * cnt;ans += 1;}// pre -> a[j - 1]if (j < n) {ll single_op = k / cnt;ll single_decrease = single_op * cnt;ll cnt_op = (cur - a[j] - 1) * cnt / single_decrease;ans += cnt_op;cur = cur - cnt_op * single_op;pre = cur * cnt;}i = j - 1;}cout << ans << "\n";
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;//cin >> T;while (T--) {solve();}return 0;
}