P1667 数列（离散化+思维）

对于一个区间【x,y】，设这个区间的总和Σa[i](从i==x 到 i==y)。

那么我们在前缀和（设为sum【i】）的意义上考虑到原操作其实就是sum【x-1】+= S，sum【x】+ S - S，sum【y】 -= S，sum【y+1】+ S - S。

而我们可以看出，原来就有sum【x-1】+ S == sum【y】，所以观察到其实原操作只是单纯的交换了一下sum【x-1】和 sum【y】而已，而且这个【x，y】区间任意选择，故原题可化为：

给一个前缀和序列，可以在其中任意交换2个数，最后让这个序列变为单调递增的。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e5+20;
 5 ll a[maxn],b[maxn],ans;
 6 
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     bool flag = true;
12     for(int i=1;i<=n;i++){
13         int c;
14         scanf("%d",&c);
15         b[i]=a[i]=a[i-1]+c;
16         if( a[i]<=0 ) flag = false;///如果有0或负数直接退出
17     }
18 
19     if( !flag ) printf("-1
");
20     else{
21         sort(b+1,b+n+1);///只用知道相对大小，所以离散化就好了
22         for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
23         
24         for(int i=1;i<=n;i++){
25             while( a[i]!=i ){///我们知道，对于每一步交换，我们只要做到有一个位置“归位”就好，
26                 swap(a[i],a[a[i]]);
27                 ans++;
28             }
29         }
30         printf("%lld
",ans);
31     }
32     return 0;
33 }