佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：
(b1, b2,... bm -1, bm)
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗?
对于30%的数据，n <= 1000；
对于全部的数据，n <= 50000。
这个题又很可惜地一个细节没有考虑清楚。大致思路完全正确。
结果还是只拿了60分 WA了4个点
一看这个题就是一个类似置换的问题。
肯定要和图论连边一样考虑的。
我们首先要有两个环，一个是最终状态的环，一个是初始状态的环（即1~n
首先判断不合法。
如果存在一个人喜欢另外一个人，但是TA喜欢的人不喜欢TA，就凉凉了。
然后就是合法情况了。
发现，这个命令就是一个置换环，
最终的所有代价就是所有环的长度。
但是，每次两个环的对正方式不同，有n种，（对正方式即：一个环不动，另一个环绕着转，每一个位置对应的数对（映射），就是一种对应方式，显然有n种）
每次连边 dfs还要n，所以就是n^2了。TLE
考虑优化。
发现这个连环跑dfs没办法优化 (lll￢ω￢)
所以要发现更深处的东西。
发现，一种对正方式下，代价，即总环长，就是位置要动的人的个数。
证明：每一个位置不同的都要动。
由于合法，所以，这些位置一定可以连成若干个环。环长就是点数。证毕
所以，要考虑每种正对方式下的不同位置个数。
但是直接做还是n^2的。
考虑优化。
发现可以优化！( ?? ω ?? )~
当我们从一种对正方式到下一种的时候，就是把初始状态的环转一下。
不妨钦定每次都顺时针转好了。
我们只需要知道每次正对方式下，有几个点位置不用动，剩下的就是要动的了。
可以这样做：
随便找一种对正方式，假设1和1对正，算出初始状态所有的点距离目标位置需要旋转的次数（可能是负数）。
对于次数，加入一个num[i]表示次数为i的点有多少个。
统计num[i]最多的是几就好啦！~
这就表示，我要在这种随便开始的正对方式，旋转i次，就有num[i]个点不用动，n-num[i]就是代价。
但是次数是负数怎么办？？即逆时针转这么多次。
因为我们钦定每次顺时针转，所以，就(+n)%n好了。
（这里我写挂了，把负数和正数加了一个fix处理，但是对于一种正对方式，可能一个位置跨过了1到达了目标点，而这个次数我算的是负数，没有加进去。
即逆时针转a次，即顺时针转n-a次。
导致答案就偏大了）
教训：还是要注意顺序，如果开始就明白，钦定顺时针转，就不会算漏了
#include<bits/stdc++.h> using namespace std; const int N=50000+5; const int inf=0x3f3f3f3f; int n; int le[N],ri[N]; int with[N][2]; int d[N]; int num[2*N]; bool fl=true; int dis[N]; bool vis[N]; int p[N]; int ans=inf; int main() { scanf("%d",&n); int x,y; for(int i=1;i<=n;i++){ scanf("%d%d",&with[i][0],&with[i][1]); } int st=1; while(fl){ vis[st]=1; if(with[with[st][1]][0]!=st&&with[with[st][1]][1]!=st) fl=false; if(with[with[st][0]][0]!=st&&with[with[st][0]][1]!=st) fl=false; if(st==1){ le[st]=with[st][1]; ri[with[st][1]]=st; ri[st]=with[st][0]; le[with[st][0]]=st; st=with[st][1]; } else if(st!=1){ if(!vis[with[st][1]]){ le[st]=with[st][1]; ri[with[st][1]]=st; st=with[st][1]; } else if(!vis[with[st][0]]){ le[st]=with[st][0]; ri[with[st][0]]=st; st=with[st][0]; } else break; } } if(!fl){ printf("-1");return 0; } st=1; int cnt=0; do{ p[st]=cnt; cnt++; st=le[st]; }while(st!=1); for(int i=1;i<=n;i++){ dis[i]=p[i]-(i-1); num[(dis[i]+n)%n]++; } for(int i=0;i<=2*n;i++){ ans=min(ans,n-num[i]); } memset(num,0,sizeof num); memset(dis,0,sizeof dis); p[1]=n; for(int i=1;i<=n;i++){ dis[i]=p[i]-(n-i+1); num[(dis[i]+n)%n]++; } for(int i=0;i<=2*n;i++){ ans=min(ans,n-num[i]); } printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/Miracevin/p/9571720.html