「Codeforces 1244E」Minimizing Difference
题目传送门
题意
给定一个长度为 \(n\) 的序列 \(a\)，一次操作可以将序列中的某个数 \(+1\) 或 \(-1\)。
定义一个序列的差值为序列的最大值减去最小值得到的数。
求进行至多 \(k\) 次操作后序列差值的最小值。
\(n\le 10^5,a_i\le 10^9,k\le 10^{14}\)
题解
显然可以二分答案 \(x\)，然后就是求使得差值 \(\le x\) 需要进行至少多少次操作。
将 \(a_i\) 排序，假设最后的序列中的数在 \([p,p+x]\) 中，记序列中最后一个 \(< p\) 的数为 \(a_l\)，第一个 \(>p+x\) 的数为 \(a_r\)，那么需要进行的操作数量是 \(p\times l-\sum_{i=1}^{l}a_i+\sum_{i=r}^{n}a_i-(p+x)\times (n-r+1)\)。根据这个式子我们可以发现 \(p\) 和 \(p+x\) 这两个数中一定有一个数是存在于原序列中的，否则可以进行调整使得操作次数更少。于是我们枚举所有情况进行判断即可。
时间复杂度 \(O(n\log \max a_i)\)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
long long read(){
register long long x = 0;
register char f = 1, ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f ^= 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return f ? x : -x;
}
#define N 100005
int n;
long long k, a[N], sum[N];
bool check(int x){
for (register int i = 1, j = 1; i <= n; ++i){
while (j <= n && a[j] - a[i] <= x) ++j;
if (a[i] * (i - 1) - sum[i - 1] + sum[n] - sum[j - 1] - (a[i] + x) * (n - j + 1) <= k) return 1;
}
for (register int i = 1, j = 1; i <= n; ++i){
while (a[i] - a[j] > x) ++j;
if ((a[i] - x) * (j - 1) - sum[j - 1] + sum[n] - sum[i] - a[i] * (n - i) <= k) return 1;
}
return 0;
}
int main(){
n = read(), k = read();
for (register int i = 1; i <= n; ++i) a[i] = read();
std :: sort(a + 1, a + 1 + n);
for (register int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
int l = 0, r = a[n] - a[1], md, ans = 0;
while (l <= r) if (check(md = (l + r) >> 1)) r = md - 1, ans = md; else l = md + 1;
printf("%d\n", ans);
}
|
