题解：P12605 求和

AutumnMoon · 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;
}