题解 P1667 【数列】

· · 题解

2021.11.7 update:

补充了被hack的问题。(格式可能略有些不符合新版规定，看在本来是一楼题解的份上放我一马吧呜呜）

对于一个区间 [x,y] ,设这个区间的总和 \sum\limits_{i=x}^ya[i] 设为 S ;

那么我们在前缀和（设为 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（自己证吧，我懒癌犯了。。）

对于这个新问题，我们先离散化，然后找“循环节”，就可以了。

不知道循环节的小伙伴看这里（其他人可以走了）：

对于一个数列，我们想把它变成单调递增的该最少交换几次呢？

我们知道，若是交换必须是相邻的就是一道逆序对水题了（P1774）,而现在任意交换，那么我们这么考虑：

采用贪心的思想：每个数都有一个自己的位置，那么我们就每当遇到一个位置上面的数不正确，就把应该在这个位置的数和当前这个位置的数互换。这样可以想到，最多换 n 次（好吧是 n-1 ）我们就可以得到正确的数列了,而其实呢，你每次换的时候很可能不止满足了当前位置的数正确了，另一个位置的数可能刚刚好“碰对了”，所以最好的结果次数就会减少，最坏情况下n-1次的最后一次一定会换一次满足两个位置，这也就是一个循环节。

而事实上，我们在换的时候若是每次都可以满足两个位置（太好了！），那么就是 n/2 次了，这时候其实是两个数一个循环节。若是3个数用2次交换满足了，（一次普通，一次满足2个位置），那么这3个数就是一个循环节，每个循环节的交换次数为循环节的长度-1。

所以我们要尽可能的找更多的循环节，那怎么办呢？（其实上面那个第一次的贪心的思想就是正解。。）

我们发现，若是有3个数成循环节，那么我就算把其中的数的位置换了，也不会破坏这个循环节（交换是在数列里任意两个数）,所以，其实我不用刻意去找循环节（它会自己来找你。。。），我只要每次都保证我的每一步交换都至少有一个位置上的数正确了，最后剩下的数的循环节一定还能使用，从而减小交换次数。

所以，说了这么半天原来

这么水？？！！

希望大家听懂了。

tip:其实那个贪心的交换不好实现，（逃

code：

#include<bits/stdc++.h>
using namespace std;
int a[100010],p[100010],s[100010],stmp[100010];
inline bool cmp(int x,int y){
    return s[x]<s[y];
}
inline void halt(){
    puts("-1"); exit(0);
}
int main(){
    int n,mx=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        p[i]=i;s[i]=s[i-1]+a[i],stmp[i]=s[i];
        mx=stmp[n];
    }
    sort(stmp+1,stmp+1+n);
    if(stmp[1]<=0 || stmp[n]!=mx) halt();
    for(int i=1;i<n;i++) if(stmp[i]==stmp[i+1]) halt();
    sort(p+1,p+1+n,cmp);//该排在第i的数的位置为p[i] 
    for(int i=1;i<=n;i++) s[p[i]]=i;//成功离散化 
    int ans=n;//不能是n-1哦
    for(int i=1;i<=n;i++){
        if(s[i]==i) ans--;
        else{
            swap(p[s[i]],p[i]),swap(s[p[s[i]]],s[i]);
        }//这里的两个swap自己找一组数去模拟着理解,其实实现的就是上面那个贪心
    }
    cout<<ans<<endl;
    return 0;
}