CF1775E TheHumanEquation TJ

发现想要让原数组全为0，前缀和数组一定也全为0

那么我们对于前缀和操作，把他变为全为0，这个时候原数组一定也全为0

因为我们的操作非常的自由 可以想对哪个数加就加 想对哪个数减就减

而在原数组上的加减也就对应了在前缀和数组上的一个区间的加减（r的地方加减抵消了 后面的不受影响）

于是问题就转化成了用一堆区间操作（区间之间可以不连在一起 也就是说一次操作可以同时操作很多个区间一起+1 或者一起-1）如何用最少的操作次数将前缀和数组变为零

显然 答案是正数最大值加上负数最小值的绝对值

#include<bits/stdc++.h>
using namespace std;#define int long long
#define endl '\n'const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f;int t;
int n;
int a[N];
int add_cnt[N];
int Max=-INF;
int Min=INF;
int ans=0;void init(){Max=-INF;Min=INF;ans=0;
}void solve(){init();cin>>n;for(int i=1;i<=n;i++){cin>>a[i];add_cnt[i]=add_cnt[i-1]+a[i];if(add_cnt[i]>0)Max=max(Max,add_cnt[i]);else Min=min(Min,add_cnt[i]);}if(Max!=-INF)ans+=Max;if(Min!=INF)ans+=-Min;cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>t;while(t--){solve();}return 0;
}