首先把这个圈看做一个图，每个同学看做一个顶点。因为要形成环，所以每个顶点的度必须为2。

如果存在度数不为2的顶点，那么整个图无法构成一个环，即“无论怎么调整都不能符合每个同学的愿望”输出-1。

如果是一个环，那么就遍历图，生成以第1个顶点为开头的序列。现在就要求出最小移动的代价。

在理解题意所述的调整方式中，要注意实际上就是把M个在错误位置上的人移动到正确的位置上，代价为M。一次下令移动即可。

假如生成的目标序列为1,5,3,2,4。我们现在就需要比较它和初始状态1,2,3,4,5，看有几个人离开了原来的位置。但这个序列实际代表的是一个环，而且方向正反有两种，就需要把初始序列正反分别转N次，和得到的序列比较，看其中最少有几个位置上的人编号不相同，就得到了我们要求的最小代价。

上述方法有大量冗余。但可以发现转来转去不管怎么转，任意两个人之间的相对位置关系在这过程中都不会变。于是想到做差，如果差小于0则加上N。

1 5 3 2 4

- 1 2 3 4 5

---|---|---|---|

0 3 0 3 4

这表示序列1,5,3,2,4不转动时1,3两个人在原来的位置上，转动3个位置后5和2两个人在原来的位置上，转动4个位置后只有4一个人会在原来的位置上。这就是说，1,5,3,2,4与1,2,3,4,5在旋转后最多有2个位置上的人编号相同，即最少有3个位置上的人编号不相同。同理要反转再求一次。

记录每个不同的差值的个数，取其最大值P，即不调换次数最大的。结果N-P就是调换次数最小的。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

切记：重新构图时一定要对数组清空！我的第一次只有50分，就是这个原因！

这题可以用C++这样做么？？

#include

#include

using namespace std;

long N,seq[50001],p=1;

class{

private:

long nbr[50001][3];

bool flag[50001];

bool isnbr(long v1,long v2){

for(int i=1;i nbr1 >> nbr2;

if(!G.AddE(i,nbr1)||!G.AddE(i,nbr2)){

cout

难理解,不过算法很精妙

天，把(p[i]-i+n)mod n理所当然地打成了abs(p[i]-i)

结果一直50分……还一直以为自己构造错了……

ps 我可以过楼下的范例哦

ms楼下的程序不能处理这种反例（测试数据还是不够强啊）

6

2 3

1 3

1 2

5 6

4 6

4 5

应该输出-1的吧？因为是两个环

var a,b:array[0..50000]of longint;

c:array[0..50000,1..2]of longint;

d:array[0..50000]of boolean;

i,j,k,m,n,max:longint;

can:boolean;

begin

readln(n);

for i:=1 to n do

readln(c,c);

b[0]:=c[1,1]; b[n]:=c[1,1];

fillchar(d,sizeof(d),0);

k:=1;

can:=true;

for i:=1 to n-1 do

begin

if d[k] then can:=false;

b[i]:=k; d[k]:=true;

if b=c[k,1] then k:=c[k,2]

else if b=c[k,2] then k:=c[k,1]

else can:=false;

if not can then break;

end;

if can then

if b[n]k then can:=false;

if can then

begin

max:=-1;

fillchar(a,sizeof(a),0);

for i:=1 to n do

inc(a[(b[i]-i+n) mod n]);

for i:=0 to n-1 do

if a[i]>max then max:=a[i];

fillchar(a,sizeof(a),0);

for i:=1 to n do

inc(a[(b[n-i+1]-i+n)mod n]);

for i:=1 to n-1 do

if a[i]>max then max:=a[i];

writeln(n-max);

end

else

writeln(-1);

end.

我在做镜像时把原先max直接覆盖上了,注意

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

挺烦人的题目

program fire(input,output);

var

n,i,j,k,max,v:longint;

a:array[0..100000,1..2] of longint;

b,c:array[0..100000] of longint;

begin

readln(n);

for i:=1 to n do readln(a,a);

for i:=1 to n do

　　 begin

　　　　k:=0;

　　　　if a[a,1]i then inc(k);

　　　　if a[a,2]i then inc(k);

　　　　if a[a,1]i then inc(k);

　　　　if a[a,2]i then inc(k);

　　　　if (k=4) or (k=3)

　　　　then begin

　　　　　　 writeln('-1');

　　　　　　 exit

　　　　　　 end

　　 end;

b[1]:=1;i:=2;k:=a[1,1];j:=1;

repeat

　　b[i]:=k;

　　inc(i);

　　v:=k;

　　if a[k,1]j

　　then k:=a[k,1]

　　else k:=a[k,2];

　　j:=v;

until i=n+1;

fillchar(c,sizeof(c),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);max:=0;

for i:=1 to n do inc(c[(b[n-i+1]-i+n)mod n]);

for i:=n-1 downto 0 do

　　 if c[i]>max

　　 then max:=c[i];

writeln(n-max);

end.

#include

#include

const int maxn=50010;

int n;

int f[maxn][2];

int goal[maxn];

int ans=maxn;

int hash[maxn];

bool SET_ORI(){

bool flag[maxn];

memset(flag, true, sizeof(flag));

goal[1]=1; flag[1]=false;

for (int i=1; ij?j:i;

}

int HASH(){

for(int i=1; i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

CHEAT的...

回447389831:

exit换成halt

艺术p245

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

求不在位置上的人数

a【i】 第i位上的同学编号

for i:=1 to n do

begin

inc(b[(a[i]-i+n) mod n])

end;

max:=0;

for i:=0 to n-1 do

if b[i]>max then max:=b[i];

fillchar(b,sizeof(b),0);

for i:=1 to n do

begin

inc(b[(a[i]-(n-i+1)+n)mod n]);//对称

end;

for i:=0 to n-1 do

if b[i]>max then max:=b[i];

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：运行超时...

├ 测试数据 03：运行时错误...|错误号: -1073741819

├ 测试数据 04：运行时错误...|错误号: -1073741819

├ 测试数据 05：运行时错误...|错误号: -1073741819

├ 测试数据 06：运行时错误...|错误号: -1073741819

├ 测试数据 07：运行时错误...|错误号: -1073741819

├ 测试数据 08：运行时错误...|错误号: -1073741819

├ 测试数据 09：运行时错误...|错误号: -1073741819

├ 测试数据 10：运行时错误...|错误号: -1073741819

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

怎么会这样？？？

#include

#include

using namespace std ;

int hash[50001];

int n , i , j , t , maxs(0) ;

inline void HASH ( int e[] )

{

for ( i = 1 ; i > n ;

int e[n+1] , h[n+1][2] , e2[n+1];

bool f[n+1] ;

for ( i = 1 ; i > h[i][0] >> h[i][1] ;

}

e[1] = 1 ;

f[1] = true ;

for ( i = 2 ; i

“置换群思想...今天刚明白...

先构造新数列(要构造两次,否则只有70分),然后向右计算相对位置差,然后累加记录数组,然后用N减去相对位置差累加值最大的,就是答案... ”

这是真的

置换群的基本概念

利用原序列和目标序列每个元素的绝对位置差来求出原序列每个元素对于目标序列的相对位置，找相对位置相同的最多的元素数，用总元素数减去它即为结果。

program fire(input,output);

var

n,i,j,k,max,v:longint;

a:array[0..100000,1..2] of longint;

b,c:array[0..100000] of longint;

begin

readln(n);

for i:=1 to n do readln(a,a);

for i:=1 to n do

　　 begin

　　　　k:=0;

　　　　if a[a,1]i then inc(k);

　　　　if a[a,2]i then inc(k);

　　　　if a[a,1]i then inc(k);

　　　　if a[a,2]i then inc(k);

　　　　if (k=4) or (k=3)

　　　　then begin

　　　　　　 writeln('-1');

　　　　　　 exit

　　　　　　 end

　　 end;

b[1]:=1;i:=2;k:=a[1,1];j:=1;

repeat

　　b[i]:=k;

　　inc(i);

　　v:=k;

　　if a[k,1]j

　　then k:=a[k,1]

　　else k:=a[k,2];

　　j:=v;

until i=n+1;

fillchar(c,sizeof(c),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);max:=0;

for i:=1 to n do inc(c[(b[n-i+1]-i+n)mod n]);

for i:=n-1 downto 0 do

　　 if c[i]>max

　　 then max:=c[i];

writeln(n-max);

end.

90 分,牛人门帮看下把