题意：
给 N N N个数，每个数的范围为 [ 1 , W ] [1,W] [1,W]，通过以下两种操作将所有的数都变成一样的，问最小操作数是多少。
- 操作一个数 + 1 +1 +1，即 a [ i ] = ( a [ i ] + 1 > W ? 1 : a [ i ] + 1 ) a[i]=(a[i]+1>W?1:a[i]+1) a[i]=(a[i]+1>W?1:a[i]+1)
- 操作一个数 − 1 -1 −1，即 a [ i ] = ( a [ i ] − 1 < 1 ? W : a [ i ] − 1 ) a[i]=(a[i]-1<1?W:a[i]-1) a[i]=(a[i]−1<1?W:a[i]−1)
分析：
这道题里对每个数
+
1
,
−
1
+1,-1
+1,−1是可以溢出的，若没有溢出的话，很明显求个中位数即可。但是这里有溢出的操作的话，就需要比较哪种操作更好了。
假设最终数组里数都变成了
v
a
l
val
val，通过观察可以发现
v
a
l
val
val一定是原数组
a
[
1...
n
]
a[1...n]
a[1...n]中的其中一个，为什么？下面我们来证明这个结论：
因为
v
a
l
!
=
a
[
1...
n
]
val!=a[1...n]
val!=a[1...n]，假设此时数组
a
a
a从小到大有序，那么有小于
v
a
l
val
val的最大下标
i
i
i，有大于
v
a
l
val
val的最小下标
j
j
j，假设当前有
x
x
x个数已经变成了
a
[
i
]
a[i]
a[i]，那么有
n
−
x
n-x
n−x个数变成了
a
[
j
]
a[j]
a[j]，那么还需操作
x
∗
(
v
a
l
−
a
[
i
]
)
+
(
n
−
x
)
∗
(
a
[
j
]
−
v
a
l
)
x*(val-a[i])+(n-x)*(a[j]-val)
x∗(val−a[i])+(n−x)∗(a[j]−val)次，才能让所有的数都变成
v
a
l
val
val。
考虑下面两种情况，无论哪一种，都可以得到更少的操作次数:
- x ≤ n − x x\leq n-x x≤n−x. 如果将所有的数都变成 a [ j ] a[j] a[j]，那么还需操作 x ∗ ( a [ j ] − a [ i ] ) x*(a[j]-a[i]) x∗(a[j]−a[i])次，等同于 x ∗ ( v a l − a [ i ] ) + x ∗ ( a [ j ] − v a l ) x*(val-a[i])+x*(a[j]-val) x∗(val−a[i])+x∗(a[j]−val)，因为 x ≤ n − x x\leq n-x x≤n−x，显然操作次数更少；
- x ≥ n − x x\geq n-x x≥n−x. 如果将所有的数都变成 a [ i ] a[i] a[i]，那么还需操作 ( n − x ) ∗ ( a [ j ] − a [ i ] ) (n-x)*(a[j]-a[i]) (n−x)∗(a[j]−a[i])次，等同于 ( n − x ) ∗ ( v a l − a [ i ] ) + ( n − x ) ∗ ( a [ j ] − v a l ) (n-x)*(val-a[i])+(n-x)*(a[j]-val) (n−x)∗(val−a[i])+(n−x)∗(a[j]−val)，显然操作次数更少。
所以最终一定是变成 a [ 1... n ] a[1...n] a[1...n]中的某个初始值。
那么首先对数组 a a a排序，然后依次遍历每个值，现在让我们来考虑对于每一个 a [ i ] a[i] a[i]，应该如何计算操作次数。
- j < i j<i j<i时， c n t _ o p = m i n ( a [ i ] − a [ j ] , a [ j ] + W − a [ i ] ) cnt\_op=min(a[i]-a[j],a[j]+W-a[i]) cnt_op=min(a[i]−a[j],a[j]+W−a[i])
- j > i j>i j>i时， c n t _ o p = m i n ( a [ j ] − a [ i ] , W − a [ j ] + a [ i ] ) cnt\_op=min(a[j]-a[i],W-a[j]+a[i]) cnt_op=min(a[j]−a[i],W−a[j]+a[i])
对于
j
<
i
j<i
j<i这一段来说，
a
[
i
]
−
a
[
j
]
a[i]-a[j]
a[i]−a[j]是随着
j
j
j的增大递减的，
a
[
j
]
+
W
−
a
[
i
]
a[j]+W-a[i]
a[j]+W−a[i]是递增的，也就是说这两个值之间存在某个交点
k
k
k，在
[
1
,
k
−
1
]
[1,k-1]
[1,k−1]这一段中最小值是
a
[
j
]
+
W
−
a
[
i
]
a[j]+W-a[i]
a[j]+W−a[i]，在
[
k
,
i
]
[k,i]
[k,i]这一段中最小值是
a
[
i
]
−
a
[
j
]
a[i]-a[j]
a[i]−a[j]，所以用二分求出
k
k
k的位置(第一个位置使得
a
[
i
]
−
a
[
k
]
≤
a
[
k
]
+
W
−
a
[
i
]
a[i]-a[k]\leq a[k]+W-a[i]
a[i]−a[k]≤a[k]+W−a[i])，
j
<
i
j<i
j<i这一段的操作数就是
(
k
−
1
)
∗
(
W
−
a
[
i
]
)
−
∑
j
=
1
k
−
1
a
[
j
]
+
(
i
−
k
+
1
)
∗
a
[
i
]
−
∑
j
=
k
i
a
[
j
]
(k-1)*(W-a[i])-\sum_{j=1}^{k-1}a[j]+(i-k+1)*a[i]-\sum_{j=k}^ia[j]
(k−1)∗(W−a[i])−∑j=1k−1a[j]+(i−k+1)∗a[i]−∑j=kia[j].
对于
j
>
i
j>i
j>i这一段来说，
a
[
j
]
−
a
[
i
]
a[j]-a[i]
a[j]−a[i]随着
j
j
j的增大递增，
W
−
a
[
j
]
+
a
[
i
]
W-a[j]+a[i]
W−a[j]+a[i]递减，同样用二分找到
k
k
k的位置使得
a
[
k
]
−
a
[
i
]
≤
W
−
a
[
j
]
+
a
[
i
]
a[k]-a[i]\leq W-a[j]+a[i]
a[k]−a[i]≤W−a[j]+a[i]成立的最后一个位置，然后需要的操作数就是
∑
j
=
i
+
1
k
a
[
j
]
−
(
k
−
i
)
∗
a
[
i
]
+
(
n
−
k
)
∗
(
w
+
a
[
i
]
)
−
∑
j
=
k
+
1
n
a
[
j
]
\sum_{j=i+1}^ka[j]-(k-i)*a[i]+(n-k)*(w+a[i])-\sum_{j=k+1}^na[j]
∑j=i+1ka[j]−(k−i)∗a[i]+(n−k)∗(w+a[i])−∑j=k+1na[j].
将两段加起来即为总的操作数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t, tt = 0;
cin >> t;
while (t--) {
int n, w;
cin >> n >> w;
vector<ll> a(n+1), pre(n+1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a.begin()+1, a.end());
for (int i = 1; i <= n; i++) {
pre[i] = pre[i-1] + a[i];
}
ll res = LONG_LONG_MAX;
for (int i = 1; i <= n; i++) {
ll sum = 0;
int l = 1, r = i, mid;
// 这里取右端点，原因是可能在i=1的位置就有rvalue <= lvalue
while (l < r) {
mid = (l + r) / 2;
ll lvalue = w - a[i] + a[mid], rvalue = a[i] - a[mid];
if (lvalue == rvalue) {
l = r = mid;
}
if (lvalue < rvalue) {
l = mid+1;
} else {
r = mid;
}
}
sum += ((l-1) * (w - a[i]) + pre[l-1]) +
((i-l+1) * a[i] - (pre[i] - pre[l-1]));
l = i, r = n;
// 这里取左端点，原因可能是在i=n的位置才有rvalue <= lvalue
while (l < r) {
mid = (l + r + 1) / 2;
ll lvalue = a[mid] - a[i], rvalue = w - a[mid] + a[i];
if (lvalue == rvalue) {
l = r = mid;
}
if (lvalue < rvalue) {
l = mid;
} else {
r = mid - 1;
}
}
sum += ((pre[l] - pre[i]) - (l-i) * a[i]) +
((n - l) * (w + a[i]) - (pre[n] - pre[l]));
res = min(res, sum);
}
cout << "Case #" << ++tt << ": ";
cout << res << endl;
}
}