自动搬运

查看原文

来自洛谷，原作者为

	人殇物已非 这家伙很勤快，什么都留下了

搬运于2025-08-24 21:27:43，当前版本为作者最后更新于2018-08-16 15:45:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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