/*
先解释一下样例，合理的安排顺序是 1 4 2 3
因为是一道noip题所以题解百度上很多了自己看一下~
关键是要注意
1.怎么判断最小代价
2.一定不要忘了这是个环，所以还要试着逆序推一遍
http://wenku.baidu.com/view/878beb64783e0912a2162aa7.html
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=50005;
int n,near[maxn][3];
int target[maxn]/*目标序列*/,same[maxn];
bool use[maxn];

void init()
{
    cin>>n;
    int l,r;
    for (int i=1;i<=n;++i)
    {
        cin>>l>>r;
        near[i][1]=l;
        near[i][2]=r;
    }
}

void work()
{
    target[1]=1;
    use[1]=1;
    for (int i=1;i<=n-1;++i)     /*构建目标序列*/
    {
        if (!use[near[target[i]][1]])//如果目前点想坐的人没有被选
        {
            target[i+1]=near[target[i]][1];//选上
            use[near[target[i]][1]]=1;//标记已经选了
        }
        else if (!use[near[target[i]][2]])//目前点想坐的人没有被选
        {
            target[i+1]=near[target[i]][2];//选上
            use[near[target[i]][2]]=1;//标记
        }
        else//有冲突
        {
            puts("-1");
            return;
        }
        //注意此构造方法的合理性，如果方案正确，那么一定是如果A想和B坐，B一定想和A坐，
        //不然根本无法完成构造，那么如果一个人被当前点一个点选放在了下一个位置，
        //那么这个人就已经满足了一个心愿，接下来就直接将另一个"心愿人物"放在他右边
    }
    memset(same,0,sizeof(same));  /*顺序求解*/
    for (int i=1;i<=n;++i)
    {
        int delta=(target[i]-i+n)%n;//当i为右端点时会有负的，所以要+n取膜
        same[delta]++;//计算一遍各个点与标准位置的差距
    }
    int ans=1000000000;
    for (int i=0;i<=n-1;++i)
    {
        ans=min(ans,n-same[i]);//相当于枚举了顺序(环)，看以哪个点为头更优
    }
    memset(same,0,sizeof(same));  /*逆序求解*/
    for (int i=1;i<=n;++i)
    {
        int delta=(target[n-i+1]-i+n)%n;
        same[delta]++;
    }
    for (int i=0;i<=n-1;++i)
    {
        ans=min(ans,n-same[i]);//道理相同
    }
    cout<<ans<<endl;
}

int main()
{
    init();
    work();
    return 0;
}

首先明显地可以知道我们需要对于目标状态建立出一个环。如果无法建立这个环，那么结果一定是－1，当建立好环以后可以知道最小移动代价一定等于最少的不在目标位置上的人数。那么我们可以对目标环进行顺时针旋转1~n-1之中任意一个，答案就一定等于旋转中的不在自己位置上的人数最少的那样的环的状态。但是对于50000的数据，我们如果要将环旋转1~n-1次，那么总共加上判断不在自己位置上的人数时间复杂度为O(n^2),显然在限定时间内是无法出解的。因此我们进行逆向思维：不在自己位置上最少的人数就一定会等于总人数减去在自己位置上最多的人数（仔细想想），那么我们就将该问题转化为了求在自己的位置上最多的人数，这样一来，我们对初始目标环中每一个位置进行判断需要旋转多少次可以回到自己位置上，每一个人的选择都将映射到[0..n-1]的数组中，选取当中最大的情况就为所求，但是考虑到环可以反转，那么我们还需要将环再求一次镜像，就可以得到初始目标需要旋转多少次可以得到在自己位置上最多的人数的环的状态，最后通过总的人数减去它即为问题所求，时间复杂度为O(n);

这道题做了一个多小时，看了n多题解，然后自己想出来了！？
1）首先应该判断是否能形成目标序列，如果不能，直接“-1”不送……
2）如果能，我们再看最少需要多少次操作。相信大多数人（比如我这种蒟蒻）第一想法就是每次确定一个起始点，然后一位一位往后判断，找最少不同（当然，正反都要做）。显然这是O（n^2)的做法，兴冲冲交上去你会发现TLE……
于是，我们转换一下思路，找最多相同的！但什么是最多相同的呢？或者说怎么找最多相同的呢？其实就是初始序列中的点到目标序列中其所在位置的距离相等的点数最多的点的数目！这句话有点绕，我们举个例子：目标序列：1 2 3 4 5初始序列：1 4 3 5 2 那么我们对初始序列来讨论：1距目标位置距离为0（spin[0]++)4距目标位置距离为2(spin[2]++)3距目标位置距离为0(spin[0]++)5距目标位置距离为1（spin[1]++)2距目标位置距离为2（spin[2]++)好了，我们看到，spin[]数组中值最大的为spin[0]和spin[2]，这两个值都为2，也就是说最多相同为2！那么最大代价就是5-2=3！（当然，与O(n^2)算法相似，我们也要再倒着判断一边）但为什么这种做法是正确的呢？其实很好想：既然有最多的点与目标位置距离为这个值，那么这个值就可以作为一个标准，也就是说，我们把这几个点固定下来，然后围绕这几个点来更改其他的点，这样得到的答案一定是最优的。
好吧，个人表达能力不太好，自己好好想想就行了……
最后附上代码吧：

#include<iostream>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
int n,ans=INF;
int a[50005],b[50005],circle[50005],spin[50005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i]>>b[i];
    for(int i=1;i<=n;++i)
        if((a[b[i]]!=i&&b[b[i]]!=i)||(a[a[i]]!=i&&b[a[i]]!=i))
        {
            cout<<-1;
            return 0;
        }
    circle[1]=1;
    circle[2]=a[1];
    for(int i=1;i<=n;++i)
        if(a[circle[i]]==circle[i-1])
            circle[i+1]=b[circle[i]];
        else    
            circle[i+1]=a[circle[i]];
    for(int i=1;i<=n;++i)
    {
        spin[(i-circle[i]+n)%n]++;
        ans=min(ans,n-spin[(i-circle[i]+n)%n]);
    }
    memset(spin,0,sizeof(spin));
    memset(circle,0,sizeof(circle));
    circle[1]=1;
    circle[2]=b[1];
    for(int i=1;i<=n;++i)
        if(b[circle[i]]==circle[i-1])
            circle[i+1]=a[circle[i]];
        else    
            circle[i+1]=b[circle[i]];
    for(int i=1;i<=n;++i)
    {
        spin[(i-circle[i]+n)%n]++;
        ans=min(ans,n-spin[(i-circle[i]+n)%n]);
    }
    cout<<ans;
    return 0;
}

作为一道NOIP提高组的题目，它肯定是有一定难度的。_
这道题目可以尝试使用 贪心 来完成，总人数减去不需要移动的人数就是总代价，只要找到不需要移动的人数最多的方案就可以达到目标了。
这道题目甚至可以认为是 置换群 的知识，但是似乎没有那么复杂。我们先来看c++代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dot[50001][2],que[50001][2],ch[50001],n;
bool used[50001];
bool make_it()
{
    register int pre;
    register int node=1;
    for(register int i=1;;i++)
    {
        pre=node;
        que[i][0]=node;
        used[node]=1;
        if(i==n)
            break;
        if(!used[dot[node][0]])
            node=dot[node][0];
        else
            if(!used[dot[node][1]])
                node=dot[node][1];
            else
                return 0;
        if(dot[node][0]!=pre&&dot[node][1]!=pre)
            return 0;
    }
    if(dot[node][0]!=1&&dot[node][1]!=1)
        return 0;
    return 1;
}
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        scanf("%d%d",&dot[i][0],&dot[i][1]);
    if(!make_it())
        return !printf("-1\n");
    register int maxn=0;
    for(register int i=1;i<=n;i++)
        que[n-i+1][1]=que[i][0];
    for(register int k=0;k<=1;k++)
    {
        memset(ch,0,sizeof(ch));
        for(register int i=1;i<=n;i++)
            ch[(que[i][k]-i+n)%n]++;
        for(register int i=0;i<n;i++)
            maxn=max(maxn,ch[i]);
    }
    return !printf("%d",n-maxn);
}

然后我们再来看一下问题。我们看到，主函数部分在输入后进行了一个特判——接下来我们就来解释一下。
这是对于无解的判断：如果目标环存在，则一定有解。否则无解。
这里的方法是进行一次遍历，如果能够正好经过N个点，则有解，否则无解。
剩下的，可以参照前面的题解理解不同算法的相似之处，也可以通过阅读代码理解一些细节和算法。
良心提醒： （n^2）算法会爆
这道题目是一个好题，值得仔细思考，自己手写算法和代码，对将来实际应用有帮助。

达成成就 **AC100 ** 纪念！！！
测试数据 #0: Accepted, time = 0 ms, mem = 1632 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1636 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1636 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1636 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1632 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 1632 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1632 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1636 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1636 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1632 KiB, score = 10
Accepted, time = 107 ms, mem = 1636 KiB, score = 100
-----------------------------------华丽的分割线-----------------------------------
```pascal
type int=longint;
var
n,i,max:int;
a:array[0..50000,1..2]of int;
b,c:array[0..50000]of int;
u:array[0..50000]of boolean;
function hunter:boolean;
var
i,z,now:int;
begin
b[1]:=1;
z:=1;
u[1]:=true;
for i:=2 to n do
begin
if u[a[z,1]]=false then now:=a[z,1]
else if u[a[z,2]]=false then now:=a[z,2]
else exit(false);
if (a[now,1]<>z) and (a[now,2]<>z) then exit(false);
b[i]:=now;
z:=now;
u[now]:=true;
end;
if (a[now,1]<>1) and (a[now,2]<>1) then exit(false);
exit(true);
end;

begin
read(n);
for i:=1 to n do read(a[i,1],a[i,2]);
if not hunter then writeln(-1) else
begin
max:=0;
for i:=1 to n do inc(c[(b[i]-i+n)mod n]);
for i:=0 to n-1 do if c[i]>max then max:=c[i];
fillchar(c,sizeof(c),0);
for i:=1 to n do inc(c[(b[i]+i)mod n]);
for i:=0 to n-1 do if c[i]>max then max:=c[i];
writeln(n-max);
end;
end.
```
我在秋名山等你！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50005;
int n,near[maxn][3];
int target[maxn],same[maxn];
bool use[maxn];

void init()
{
scanf("%d",&n);
int l,r;
for (int i=1;i<=n;++i)
{
scanf("%d%d",&l,&r);
near[i][1]=l;
near[i][2]=r;
}
}

void work()
{
target[1]=1;
use[1]=1;
for (int i=1;i<=n-1;++i) /*构建目标序列*/
{
if (!use[near[target[i]][1]])
{
target[i+1]=near[target[i]][1];
use[near[target[i]][1]]=1;
}
else if (!use[near[target[i]][2]])
{
target[i+1]=near[target[i]][2];
use[near[target[i]][2]]=1;
}
else
{
puts("-1");
return;
}
}
memset(same,0,sizeof(same)); /*顺序求解*/
for (int i=1;i<=n;++i)
{
int delta=(target[i]-i+n)%n;
same[delta]++;
}
int ans=1000000000;
for (int i=0;i<=n-1;++i)
{
ans=min(ans,n-same[i]);
}
memset(same,0,sizeof(same)); /*逆序求解*/
for (int i=1;i<=n;++i)
{
int delta=(target[n-i+1]-i+n)%n;
same[delta]++;
}
for (int i=0;i<=n-1;++i)
{
ans=min(ans,n-same[i]);
}
printf("%d",ans);
}

int main()
{
init();
work();
return 0;
}

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int Maxn=50010;
int Dv1[Maxn],Dv2[Maxn];
//分别表示与1,2,...,n和n,n-1,...,2,1的差值
int vis[Maxn];
int c[Maxn];//目标链
int l1[Maxn],l2[Maxn];
int si=1,n,ans=0;
inline int read()//读入优化
{
int fl=1,rt=0; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') fl=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){rt=rt*10+ch-'0'; ch=getchar();}
return fl*rt;
}
void Build()//建目标链
{
c[1]=1; c[2]=l1[1]; vis[c[1]]=vis[c[2]]=1;
for(int i=2;i<=n-1;i++)
{
if(c[i-1]==l1[c[i]]) c[i+1]=l2[c[i]],vis[c[i+1]]=1;

else if(c[i-1]==l2[c[i]]) c[i+1]=l1[c[i]],vis[c[i+1]]=1;
else
{
si=0;
printf("-1\n"); return ;
}
}
for(int i=1;i<=n;i++) if(!vis[i]) si=0,printf("-1\n");
//前面没判断c[n]同学的需求是否满足，这里判断一下。
if((c[1]==l1[c[n]]&&c[n-1]!=l2[c[n]])||(c[1]!=l1[c[n]]&&c[n-1]==l2[c[n]])) si=0,printf("-1\n");
else if((c[1]==l2[c[n]]&&c[n-1]!=l1[c[n]])||(c[1]!=l2[c[n]]&&c[n-1]==l1[c[n]])) si=0,printf("-1\n");
}
void Simulation()//求答案
{
for(int i=1;i<=n;i++)
{
Dv1[(c[i]-i+n)%n]++;
Dv2[(c[n-i+1]-i+n)%n]++;
}
for(int i=0;i<=n-1;i++) ans=max(ans,max(Dv1[i],Dv2[i]));
printf("%d\n",n-ans);
}
void read_ini()
{
n=read();
for(int i=1;i<=n;i++) l1[i]=read(),l2[i]=read();
Build();
if(si) Simulation();
}
int main()
{
read_ini();
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<queue>
#include<map>
#define pa pair<int,int>
#define mod 1000000007
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,ans;
int c[50005];
int a[50005],b[50005];
bool vis[50005];
int t1[50005],t2[50005];
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=read();
c[1]=1;c[2]=a[1];
vis[c[1]]=vis[c[2]]=1;
for(int i=2;i<n;i++)
{
if(c[i-1]==a[c[i]])c[i+1]=b[c[i]];
else if(c[i-1]==b[c[i]])c[i+1]=a[c[i]];
else {puts("-1");return 0;}
vis[c[i+1]]=1;
}
for(int i=1;i<=n;i++)
if(!vis[i]){puts("-1");return 0;}
for(int i=1;i<=n;i++)
{
int t=(c[i]-i+n)%n;
t1[t]++;
ans=max(ans,t1[t]);
t=(c[n-i+1]-i+n)%n;
t2[t]++;
ans=max(ans,t2[t]);
}
printf("%d",n-ans);
return 0;
}***

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=50005;
int n,near[maxn][3];
int target[maxn],same[maxn];
bool use[maxn];

void init()
{
cin>>n;
int l,r;
for (int i=1;i<=n;++i)
{
cin>>l>>r;
near[i][1]=l;
near[i][2]=r;
}
}

void work()
{
target[1]=1;
use[1]=1;
for (int i=1;i<=n-1;++i)
{
if (!use[near[target[i]][1]])
{
target[i+1]=near[target[i]][1];
use[near[target[i]][1]]=1;
}
else if (!use[near[target[i]][2]])
{
target[i+1]=near[target[i]][2];
use[near[target[i]][2]]=1;
}
else
{
puts("-1");
return;
}
}
memset(same,0,sizeof(same));
for (int i=1;i<=n;++i)
{
int delta=(target[i]-i+n)%n;
same[delta]++;
}
int ans=1000000000;
for (int i=0;i<=n-1;++i)
{
ans=min(ans,n-same[i]);
}
memset(same,0,sizeof(same));
for (int i=1;i<=n;++i)
{
int delta=(target[n-i+1]-i+n)%n;
same[delta]++;
}
for (int i=0;i<=n-1;++i)
{
ans=min(ans,n-same[i]);
}
cout<<ans<<endl;
}

int main()
{
init();
work();
return 0;
}

#include<cstdio>
#define MAXN 50001
int a[MAXN], b[MAXN];
int s[MAXN], cnt1[MAXN], cnt2[MAXN],ans;
int i,j,n;
int main()
{
scanf("%d",&n);
for (i=1; i<=n; i++)
scanf("%d%d",&a[i],&b[i]);
s[1]=1; s[n]=a[1]; s[2]=b[1];
for (i=3; i<n; i++)
if (a[s[i-1]]==s[i-2]) s[i]=b[s[i-1]];
else s[i]=a[s[i-1]];
for (i=1; i<=n; i++)
{
int t1=i+1, t2=i-1;
if (t1>n) t1=1;
if (t2<1) t2=n;
if ((s[t1]!=a[s[i]] || s[t2]!=b[s[i]]) && (s[t2]!=a[s[i]] || s[t1]!=b[s[i]]))
{
printf("-1");
return 0;
}
}
for (i=1; i<=n; i++)
{
cnt1[(s[i]-i+n)%n]++;
cnt2[(s[i]+i-1)%n]++;
}
for (i=0; i<n; i++) //注意注意，%n后存放的地址为0..n-1。否则会爆第10个点
{
if (ans<cnt1[i]) ans=cnt1[i];
if (ans<cnt2[i]) ans=cnt2[i];
}
printf("%d",n-ans);
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 1488 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1484 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1488 KiB, score = 10
测试数据 #3: Accepted, time = 593 ms, mem = 1488 KiB, score = 10
测试数据 #4: Accepted, time = 765 ms, mem = 1484 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 1488 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 1484 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1488 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 1488 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1488 KiB, score = 10
Accepted, time = 1543 ms, mem = 1488 KiB, score = 100

连续两次理解错了题意，第一次以为m是连续的，第二次以为m是相对有序的，结果最后发现这是道大水题，这题哪还需要什么置换群的知识，很明显总人数减去不需要移动的人数就是总代价，只要找到不需要移动的人数最多的方案就行了。
```c++
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 50000 + 10;
int n, m;
int vis[maxn];
int G[maxn][2];
int B[maxn];

bool init () {
memset(vis, 0, sizeof(vis));
B[0] = 0; B[1] = G[0][0];
vis[B[0]] = vis[B[1]] = 1;
for (int i = 1; i < n-1; i++) {
if (B[i-1] == G[B[i]][0]) B[i+1] = G[B[i]][1];
else if (B[i-1] == G[B[i]][1]) B[i+1] = G[B[i]][0];
else return false;
vis[B[i+1]] = 1;
}
for (int i = 0; i < n; i++)
if (!vis[i]) return false;
return true;
}

int cnt[maxn][2];
int solve () {
for (int i = 0; i < n; i++) {
cnt[(B[i]-i+n)%n][0]++;
cnt[(B[n-i-1]-i+n)%n][1]++;
}
int ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, max(cnt[i][0], cnt[i][1]));

return n-ans;
}

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d%d", &G[i][0], &G[i][1]);
G[i][0]--; G[i][1]--;
}

if (init()) cout << solve() << "\n";
else cout << "-1\n";

return 0;
}
```

记录信息
评测状态 Accepted
题目 P1008 篝火晚会
递交时间 2015-11-06 11:19:17
代码语言 C++
评测机 VijosEx
消耗时间 252 ms
消耗内存 1556 KiB
评测时间 2015-11-06 11:19:19
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 1556 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1556 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1552 KiB, score = 10
测试数据 #3: Accepted, time = 39 ms, mem = 1556 KiB, score = 10
测试数据 #4: Accepted, time = 41 ms, mem = 1552 KiB, score = 10
测试数据 #5: Accepted, time = 37 ms, mem = 1552 KiB, score = 10
测试数据 #6: Accepted, time = 37 ms, mem = 1552 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1552 KiB, score = 10
测试数据 #8: Accepted, time = 37 ms, mem = 1552 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1556 KiB, score = 10
Accepted, time = 252 ms, mem = 1556 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dot[50010][2],que[50010][2],ch[50010],n;
bool used[50010];
bool make_it()
{
int pre;
int node=1;
for(int i=1;;i++)
{
pre=node;
que[i][0]=node;
used[node]=true;
if(i==n)break;
if(!used[dot[node][0]])node=dot[node][0];
else if(!used[dot[node][1]])node=dot[node][1];
else return false;
if(dot[node][0]!=pre&&dot[node][1]!=pre)return false;
}
if(dot[node][0]!=1&&dot[node][1]!=1)return false;
return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&dot[i][0],&dot[i][1]);

if(!make_it()){
printf("-1\n");return 0;
}
int maxn=0;
for(int i=1;i<=n;i++)que[n-i+1][1]=que[i][0];
for(int k=0;k<=1;k++){
memset(ch,0,sizeof(ch));
for(int i=1;i<=n;i++)
ch[(que[i][k]-i+n)%n]++;
for(int i=0;i<n;i++)
maxn=max(maxn,ch[i]);
}
printf("%d",n-maxn);
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=50005;
int f[maxn];
int wz[maxn];
int py[maxn][2];
int numn;
void dfs(int cur,int now)
{
if(wz[py[now][1]]==-1)
{
wz[py[now][1]]=(cur+1)%numn;
f[cur+1]=py[now][1];
dfs(cur+1,py[now][1]);
}
else if(wz[py[now][0]]==-1)
{
wz[py[now][0]]=(cur+1)%numn;
f[cur+1]=py[now][0];
dfs(cur+1,py[now][0]);

}
else if(cur==numn-1)return;
else {printf("-1\n");exit(0);}
}
void work()
{
int c1[maxn],c2[maxn];
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(int i=0;i<numn;i++)
{
c1[(numn+i-f[i]+1)%numn]++;
c2[(numn+i+f[i]-1)%numn]++;
}
int maxx=-1;
for(int i=0;i<numn;i++)
{
maxx=max(maxx,c1[i]);
maxx=max(maxx,c2[i]);
}
printf("%d\n",numn-maxx);
}
int main()
{
scanf("%d",&numn);
memset(wz,-1,sizeof(wz));
for(int i=1;i<=numn;i++)scanf("%d%d",&py[i][0],&py[i][1]);
f[0]=1;wz[1]=0;
dfs(0,1);
for(int i=0;i<numn;i++)
{
// printf("%d ",f[i]);printf("\n");
if(!(f[(i+numn-1)%numn]==py[f[i]][0]||f[(i+numn-1)%numn]==py[f[i]][1]))
{
printf("-1\n");exit(0);
}
if(!(f[(i+numn+1)%numn]==py[f[i]][0]||f[(i+numn+1)%numn]==py[f[i]][1]))
{
printf("-1\n");exit(0);
}
}
work();
return 0;
}
看了半天题解才搞会。。。关键是题目说的很含糊！！！
主要就是先根据每个人要求建环
然后定一个人原地不动，剩下的人做调整，这里有n种情况
接着每种情况可以通过简单的优化通过O(1)时间算出代价

打‘Wrong！’有50分。。

这道题真是太好了。奇妙无穷。
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[50005];
int size;
void go(){
int i, j;
int ans = 0;
int dis[50005];
memset(dis, 0, sizeof(dis));
for (i = 1; i <= size; i++){
int d = (a[i] - i + size) % size;
dis[d]++;
}
for (i = 0; i < size; i++){
if (ans < dis[i])
ans = dis[i];
}
memset(dis, 0, sizeof(dis));
for (i = 1; i <= size; i++){
int d = (a[size+1-i]-i+size) % size;
dis[d]++;
}
for (i = 0; i < size; i++){
if (ans < dis[i])ans = dis[i];
}
cout << size-ans << endl;
}
int main(){
freopen("in.txt", "r", stdin);
int neibor[50005][2];
int i;
cin >> size;
for (i = 1; i <= size; i++){
scanf("%d%d",&neibor[i][0],& neibor[i][1]);
}
bool used[50005];
memset(used, 0, sizeof(used));
a[1] = 1;
used[1] = true;
for (i = 2; i <= size; i++){
int last = a[i - 1];
if (!used[neibor[last][0]]){
a[i] = neibor[last][0];
used[a[i]] = true;
}
else if (!used[neibor[last][1]]){
a[i] = neibor[last][1];
used[a[i]] = true;
}
else {
cout << -1 << endl;
return 0;
}
}

if (neibor[1][0] != a[size] && neibor[1][1] != a[size]){
cout << -1 << endl;
return 0;
}
go();
return 0;
}

#include<stdio.h>
#include<string.h>
int data[50001][2],shi[50001],a[50001];
int main()
{
int n,i,j,qian,hou;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&data[i][0],&data[i][1]);
}
a[1]=1;shi[a[1]]=1;
for(i=2;i<=n;i++)
{
qian=data[a[i-1]][0];
hou=data[a[i-1]][1];
if(shi[qian]==0)
{
a[i]=qian;
shi[qian]=1;
}
else if(shi[hou]==0)
{
a[i]=hou;
shi[hou]=1;
}
else
{
printf("-1");
return 0;
}
}
int temp=0,max=0;
memset(shi,0,sizeof(shi));
for(i=1;i<=n;i++)
{
temp=(n+a[i]-i+1)%n;
shi[temp]++;
}
for(i=0;i<n;i++)
{
if(max<shi[i])
{
max=shi[i];
}
}
memset(shi,0,sizeof(shi));
for(i=1;i<=n;i++)
{
temp=(n+a[n-i+1]-i+1)%n;
shi[temp]++;

}
for(i=0;i<n;i++)
{
if(max<shi[i])max=shi[i];
}
printf("%d",n-max);
}

题解

从10、到30、到100。。。。。。

题解：http://blog.163.com/syf_light_feather/blog/static/223755067201362945326756/

20 30 40 50 70 分都有～泪流满面.

Accepted

100
772 2

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:55:05
Wrong Answer

70
613 1

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:53:24
Wrong Answer

70
686 2

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:45:35
Wrong Answer

70
856 2

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:42:12
Wrong Answer

70
803 2

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:37:26
Wrong Answer

70
882 1

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:22:39
Wrong Answer

70
1145 1

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:20:30
Wrong Answer

10
733 1

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:11:30
Wrong Answer

50
723 1

P1008 篝火晚会
vcvycy Pascal 2013-06-30 00:04:20
Wrong Answer

50
781 1

P1008 篝火晚会
vcvycy Pascal 2013-06-29 23:55:49
Wrong Answer

40
656 1

P1008 篝火晚会
vcvycy Pascal 2013-06-29 23:49:49
Wrong Answer

40
758 1

P1008 篝火晚会
vcvycy Pascal 2013-06-29 23:44:00
Time Exceeded

30
7160 1

P1008 篝火晚会
vcvycy Pascal 2013-06-29 23:38:22
Time Exceeded

20
7135 1

P1008 篝火晚会
vcvycy Pascal 2013-06-29 23:35:08