讨论 / 对题目的理解
崛起 2011-04-14 18:24:00
点我顶贴 收藏 删除

题目是这样叙述的:

这里m的值是由佳佳决定的,每次命令m的值都可以不同。这个命令的作用是移动编号是b1,b2,…… bm –1,bm的这m个同学的位置。要求b1换到b2的位置上,b2换到b3的位置上,……,要求bm换到b1的位置上。

b1、b2……不一定是相邻的同学

至于此种理解对与不对我也是道听途说:

from:

http://wenku.baidu.com/view/878beb64783e0912a2162aa7.html

第33张幻灯片。

#1 崛起@2011-04-14 18:24:00
回复 删除
理解正确
#2 不争不羁绊@2016-01-02 21:42:08
回复 删除
太坑了,b1 b2...bm 这很明显是连续的,而且从第一个开始,可实际上的解答,转换可以不从第一个开始,也不一定连续,不知2005多少人被坑的连样例都看不懂
#3 TenderRun@2016-01-03 02:20:28
回复 删除
#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);

}

查看更多回复
提交回复