CF1244E Minimizing Difference - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
首先容易想到把 \(a\) 升序排列。
想让 \(\max - \min\) 最小，一定是选择降低 \(\max\)，提高 \(\min\)。
先考虑一个问题：单纯最大化 \(\min\)。
想一下，提高 \(\min\) 其实是这样一个过程：一直加 \(a_1\)，直到 \(a_1 = a_2\)，然后一直同步加 \(a_1, a_2\)，直到 \(a_1=a_2=a_3\)，再一直同步加 \(a_1,a_2,a_3\)……直到最后 \(k\) 被用尽。易证不这么加就是浪费操作。
假设我们刚刚同步把 \(a_1 \sim a_{i - 1}\) 加到和 \(a_i\) 齐平，现在我们要把 \(a_1 \sim a_i\) 加到和 \(a_{i +1}\) 齐平。
如果代价足够用，我们就考虑把 \(a_1 \sim a_i\) 花费 \(i(a_i - a_{i-1})\) 的代价一直加到 \(a_{i + 1}\)，然后 \(i \gets i + 1\)；
如果代价不够用了，就考虑把 \(a_1 \sim a_i\) 一直加到代价耗尽，答案就是此时能加到的位置。
单纯降低 \(\max\) 是同理的。现在我们综合考虑。
如果我们刚刚把 \(a_1\) 加到和 \(a_2\) 齐平，这时有两条路走：
- \(a_1, a_2\) 一直加到和 \(a_3\) 齐平；
- \(a_n\) 一直减到和 \(a_{n-1}\) 齐平。
那么我们一定选择第二条路。因为第一条路每花费 \(2\) 的代价才能提高 \(1\) 的 \(\min\)，但第二条路每花费 \(1\) 的代价就能降低 \(1\) 的 \(\max\)。第二条路走完（齐平了）如果还有操作剩余，再走第一条路。
因此最优解一定是重复执行以下三步得到，初始时 \(l = 1\)：
- 尝试把 \(a\) 开头长度为 \(l\) 的前缀加到和后面那个数齐平，并把 \(a\) 结尾长度为 \(l\) 的后缀减到和前面那个数齐平；
- 如果齐平成功，\(l \gets l +1\)；
- 如果齐平不成功，说明步数要不够了。尽可能让剩下的步数给前缀的 \(l\) 个数 \(+1\)，后缀的 \(l\) 个数 \(-1\)，可以让 \(\max\) 和 \(\min\) 再靠近【剩下的步数除以 \(l\)，下取整】个单位。此时得到最终答案。
考虑前缀和后缀的汇合点。这里我们让上述算法在处理 \(l= \lfloor \dfrac{n - 1}{2} \rfloor\) 后终止。那么在 \(n\) 为奇数时刚刚好，\(n\) 为偶数时还有中间两个点没齐平，手动尝试齐平一下即可。
时间复杂度 \(\mathcal{O}(n)\)。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-10-18 09:56:47
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-10-18 10:45:39
*/
#include <bits/stdc++.h>
#define int long long
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
const int maxn = (int)1e5 + 5;
int a[maxn];
inline int min(int a, int b) {
return a < b ? a : b;
}
signed main() {
int n = read(), k = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
std :: sort(a + 1, a + 1 + n);
int ans = a[n] - a[1];
for (int l = 1, r = n; l <= ((n - 1) >> 1); ++l, --r) {
int t = (a[l + 1] - a[l] + a[r] - a[r - 1]) * l;
if (k < t) {
printf("%lld\n", ans - k / l);
return 0;
} else {
ans = a[r - 1] - a[l + 1];
// 可以写成 ans -= t / l;
k -= t;
}
}
if ((n & 1) == 0) {
int l = (n >> 1);
ans -= min(a[l + 1] - a[l], k / l);
}
printf("%lld\n", ans);
return 0;
}