题解：P14047 [SDCPC 2019] Stones in the Bucket

AA12_G · 2025-09-18 13:00:17 · 题解

思路

如果我们设一个数 x 为我们最后需要这 n 个数最后等于的一个数。

令 left=\sum^{n}_{i=1} (a_i<x)(x-a_i)，具体点的说，就是 n 个数中所有小于 x 的数到 x 还需要的石子（总）个数。

同理，定义 right=\sum^{n}_{i=1} (a_i>x)(a_i-x)。

我们发现这两种操作：

• 操作一：我们可以从任意一个桶拿出一个石头，不难发现这个操作只在 a_i>x 的桶使用是有意义的。操作后会将 right\leftarrow right-1。

• 操作二：我们可以从一个桶中拿出一个石头，放到另一个桶。不难发现，这个操作拿出石头的一个桶应满足 a_i>x，放石头的那个桶应该是 a_i<x 的。这样最优。不难发现这个操作会让 right\leftarrow right-1,left\leftarrow left-1。

最后需要的操作次数就是 right，略微思考即可得出。当 left\neq0 时，使用操作二，否则使用操作一。前提是 left\leq right。否则可以证明，当 x 不变时，无法成功。

那么说了这些，最后一个问题就是 x怎么选择？显然可以使用二分（应该是 O(n\log n)），但是时间复杂度不是很保险。

所以我们可以 O(1) 求出 x，不难发现，最优的 x 应该是 \lfloor \frac{\sum^n_{i=1}}{n} \rfloor。可以证明，这样可以保证 x 是整数而且满足 left\leq right，而且 right 最小。

代码

时间复杂度 O(\sum n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
void mian()
{
    int n;
    cin >> n;
    int a[114514], sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sum = sum / n;
    int  right = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (a[i] > sum) right += a[i] - sum;
    }
    cout << right << endl;
}
signed main()
{
    int T;
    cin >> T;
    for (int i = 1; i <= T; i ++) mian();
    return 0;
}