NOIP 2005 篝火晚会

题目说得神乎其神，不过，只要读者构造几个数据手工模拟一下，就可以发现其实很简单。

首先，大部分读者都会想到要通过输入数据构造目标串，如果不能构造目标串，那么一定无解。

可以按照这个规则构造，用final数组表示最终状态某个位置上的学员编号。首先，把1号放在final[0]，然后，按照下列规则继续：

寻找一个学员，符合如下条件：
1、与当前位置学员互相喜欢
2、还没有在final数组中。
如果找不到，就说明无解。
找到后放在下一个位置，当前位置后移，直到final数组内有N个人，构建完毕。

最后，由于实际上是环，还需要检查final数组第一个和最后一个是否互相喜欢。

下一步就是计算到达目标状态所需代价，如果可以解决这个问题，就可以通过前三个测试数据。

题目有说：

(b1, b2,... bm -1, bm)
这个命令的作用是移动编号是b1，b2，…… bm-1，bm，这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。

需要说明的是，b1,b2...不需要是连续的，也不需要是递增的，明白这一点，问题就解决一半了。

读者可以找几个数据模拟一下，可以发现问题的实质：只需要一个命令，并且这个命令的代价就是相同位置上与目标状态不同的学员人数。

证明过程：
位置 0 1 2 3 4 5
初始状态 a b c d e f
目标状态 a c e d f b
如果把上面需要移动的位置用->连接，如下：
1->5
2->1
4->2
5->4
可以发现，上面的指令构成了一个环。说明，如果有初始状态与目标状态有M个位置有差异，那么最终代价就是M。

由于学员坐成一个环，初始状态与目标状态的环可以相对运动，不同相对位置的M是不一样的，如下
初始状态 1 2 3 4 5
目标状态1 1 2 3 5 4
目标状态2 5 4 1 2 3
可以发现，两个目标状态所需的M是不一样的。
所以，需要找到最小的M。

最先想到的方法是这样：final不动，初始状态相对移动，记录不同位置下的M，取最小即可。

C语言: 高亮代码由发芽网提供

1 max = 0;
2 for(i = 0;i < N;i ++)
3 {
4     for(c = j = 0;j < N;j ++)
5         if((j + 1) == final[(i + j)]) c ++;
6     if(c > max)
7         max = c;
8 }

可是，这种算法的复杂度是n^2，50000的数据会超时。

所以……，需要更高效的算法。

观察：

A:1 2 3 4 5 6 7 8 9 10
B:1 9 10 4 6 3 5 7 2 8
C:4 6 3 5 7 2 8 1 9 10

把这三个串想象成环状的，计算一下把A中某个数字要移动到B中的位置需要向左移动多少位，然后再算一下C的。

细心的读者可以发现，如果A=移动位数出现次数最多的数的出现次数，最大匹配数M = N - A，所以，问题迎刃而解。

此外，还是由于环的原因，正向计算后还要反转final数组，再次计算M，取最小值。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MXN (50000+10)  //别忘了括号
05
06 long pair[MXN][2];
07
08 long pos[MXN];
09 long final[MXN * 3];
10 long N;
11 long c[MXN];
12
13 void create_final()
14 {
15     memset(final,0,sizeof(final));
16     long i,r,l;
17     long next;
18     final[0] = 1;
19     for(i = 0;i < N;)
20     {
21         l = pair[final[i]][0];
22         r = pair[final[i]][1];
23         if(i > 0 && l != final[i - 1])  next = l;
24         else next = r;
25         if(pair[next][0] != final[i] && pair[next][1] != final[i])
26         {
27             printf("-1\n");fclose(stdout);exit(0);
28         }
29         final[++ i] = next;
30     }
31     if(final[N] != final[0])
32     {
33         printf("-1\n");fclose(stdout);exit(0);
34     }
35 }
36
37 long count_differ()
38 {
39     long i;
40     long max;
41     memset(c,0,sizeof(c));
42     for(i = 1;i <= N;i ++)  //计算左移位数
43     {
44         if(pos[i] <= i)
45             c[i - pos[i]] ++;
46         else
47             c[N - pos[i] + i] ++;
48     }
49     max = 0;
50     for(i = 0;i <= N;i ++)
51     {
52         if(c[i] > max)  max = c[i];
53     }
54     return N - max;
55 }
56
57 int main()
58 {
59     scanf("%ld",&N);
60     long i;
61     long tmp,min;
62     for(i = 1;i <= N;i ++)
63         scanf("%ld%ld",&pair[i][0],&pair[i][1]);
64     create_final();
65     for(i = 0;i < N;i ++)
66         pos[final[i]] = i + 1;
67     min = count_differ();
68     for(i = 0;i < N;i ++)
69         pos[final[i]] = N - i;  //反转final
70     tmp = count_differ();
71     if(tmp < min)   min = tmp;
72     printf("%ld\n",min);
73     return 0;
74 }