专栏文章

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

AAA12_G
P14047题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minv8fni
此快照首次捕获于
2025/12/02 08:54
3 个月前
此快照最后确认于
2025/12/02 08:54
3 个月前
查看原文

思路

如果我们设一个数 xx 为我们最后需要这 nn 个数最后等于的一个数。
令 left=∑i=1n(ai<x)(x−ai)left=\sum^{n}_{i=1} (a_i<x)(x-a_i)，具体点的说，就是 nn 个数中所有小于 xx 的数到 xx 还需要的石子（总）个数。
同理，定义 right=∑i=1n(ai>x)(ai−x)right=\sum^{n}_{i=1} (a_i>x)(a_i-x)。
我们发现这两种操作：
  • 操作一：我们可以从任意一个桶拿出一个石头，不难发现这个操作只在 ai>xa_i>x 的桶使用是有意义的。操作后会将 right←right−1right\leftarrow right-1。
  • 操作二：我们可以从一个桶中拿出一个石头，放到另一个桶。不难发现，这个操作拿出石头的一个桶应满足 ai>xa_i>x，放石头的那个桶应该是 ai<xa_i<x 的。这样最优。不难发现这个操作会让 right←right−1,left←left−1right\leftarrow right-1,left\leftarrow left-1。
最后需要的操作次数就是 rightright，略微思考即可得出。当 left≠0left\neq0 时，使用操作二，否则使用操作一。前提是 left≤rightleft\leq right。否则可以证明，当 xx 不变时，无法成功。
那么说了这些，最后一个问题就是 x怎么选择？显然可以使用二分（应该是 O(nlog⁡n)O(n\log n)），但是时间复杂度不是很保险。
所以我们可以 O(1)O(1) 求出 xx，不难发现，最优的 xx 应该是 ⌊∑i=1nn⌋\lfloor \frac{\sum^n_{i=1}}{n} \rfloor。可以证明，这样可以保证 xx 是整数而且满足 left≤rightleft\leq right，而且 rightright 最小。

代码

时间复杂度 O(∑n)O(\sum n)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...