篝火晚会 (并没有算法)
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有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。
首先，我们需要证明对于一个置换，需要交换的次数就是置换中元素不相同的数量。所以O(n^2)的算法就是枚举初始环的一个开始点，然后和目标环比较有多少个元素相同。这样显然会超时。其实我们只要求出对于每一个元素，让初始环的这一个元素和目标环的这一个元素对齐，初始环需要转k圈，接着cnt[k]++。然后O(n)枚举初始环需要转的圈数，答案就是总人数-此置换中已经相同的人数。注意篝火晚会的圈可以对称翻转。
#include <cstdio>
#include <utility>
#include <algorithm>
const int maxn=50005;
int n, side1[maxn], side2[maxn], ans;
int loop[maxn], use[maxn], v1[maxn], v2[maxn];
//做此题前提：一个置换不相同的元素个数等于最小所要交换的元素个数
int main(){
scanf("%d", &n);
for (int i=1; i<=n; ++i)
scanf("%d%d", &side1[i], &side2[i]);
loop[1]=1; loop[2]=side1[1];
int t=2, now, pre; bool flag=true;
while (t<=n){
now=loop[t]; pre=loop[t-1];
if (side1[now]!=pre&&side2[now]!=pre){
flag=false; break; }
if (side1[now]==pre) loop[++t]=side2[now];
else loop[++t]=side1[now];
} //loop就是顺时针的篝火序列
if (loop[t]!=loop[1]) flag=false;
if (!flag){
printf("-1
"); return 0; }
//枚举这个东西的位置变成loop[i]需要圆顺时针转几圈
//注意篝火晚会的那个环可以翻转，所以有一个人可以有两个位置
for (int i=1; i<=n; ++i){
++v1[(loop[i]-i+n)%n];
++v2[(loop[i]-(n-i+1)+n)%n];
}
for (int i=0; i<n; ++i)
ans=std::max(ans, std::max(v1[i], v2[i]));
printf("%d
", n-ans);
return 0;
}