自动搬运

查看原文

来自洛谷，原作者为

	Sweet_2013 今夕是何年？ | 234粉爆我妹的照片，求关 | 互关条件 /training/813543

搬运于2025-08-24 23:16:46，当前版本为作者最后更新于2025-05-29 16:37:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：给定一个序列，可以进行若干次操作。每次操作选择两个不同的下标 $i$ 和 $j$，将 $a_i$ 加 $1$，$a_j$ 减 $1$，最后要让序列的前缀和之和等于后缀和之和，求最小的操作次数。如果无法实现，输出 $-1$。

假设前缀和之和为 $S$，后缀和之和为 $T$，题目就可以这么做：

• 求出序列的前缀和和后缀和。
• 每次选择 $i$ 和 $j$ 后并操作，这种操作不会改变序列的总和，因为 $+1$ 和 $-1$ 是可以互相抵消的。但会影响 $S$ 和 $T$ 的差值：在位置 $k$ 加 $1$ 对 $S-T$ 的影响是 $n-2k+1$，在位置 $k$ 减 $1$ 对 $S-T$ 的影响是 $−(n−2k+1)$。所以，每次操作总共对 $S-T$ 的影响就是两式相减，得到答案是 $2(j-i)$，最大可能的单次操作影响是 $2(n−1)$。
• 答案计算：
  • 如果 $S-T$ 为奇数，那么一定无解，因为每次操作改变 $S-T$ 的量为偶数，所以 $S-T$ 必须是偶数才能通过操作变为 $0$。
  • 否则，答案就是 $\lceil \frac{|S-T|}{2(n-1)} \rceil$，因为每次操作最多可以调整 $2(n−1)$ 的差值。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, a[1000005];
long long s, t, p, s1;//p 是前缀和的累加器，s1 是后缀和的累加器，s 是前缀和之和，t 是后缀和之和。 
int main() {
    cin>> n;
    for(int i=0;i<n;i++) cin>> a[i];
    if(n==1) {
        cout<<0;
        return 0;
    }//特判，n 为 1，就说明 S 和 T 已经相同了，所以是操作 0 次。
    for(int i=0;i<n;i++) {
        p+=a[i];
        s+=p;
    }//计算前缀和。
    for(int i=n-1;i>=0;i--) {
        s1+=a[i];
        t+=s1;
    }//计算后缀和。
    if((s-t)%2!=0) cout<<-1;// S-T 为奇数，但每次操作变化的数为偶数，所以肯定无解。
    else cout<<(abs(s-t)+(2*n-2)-1)/(2*n-2);
    return 0;
}