本文共 2758 字,大约阅读时间需要 9 分钟。
描述
佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有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。
格式
输入格式
输入的第一行是一个整数n(3 <= n <= 50000),表示一共有n个同学。其后n行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是1的同学最希望相邻的两个同学的编号,编号是2的同学最希望相邻的两个同学的编号,……,编号是n的同学最希望相邻的两个同学的编号。
输出格式
输出包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望,则输出-1。
样例
样例输入
43 44 31 21 2
样例输出
2
限制
1s
来源
NOIp2005 第三题
一开始真不会 感觉 这tm怎么做啊。。。
后来自己读题
原来b1,b2......bm与1,2,3......m没有任何关系
b1可以是1 可以是2 也可以是3...
那么这样的话 所有位置不匹配的 一次就可以换对位置!
我们就要去找位置不匹配的最小人数
(据说这是置换群,蒟蒻表示真心不知道。。。)
首先判断-1 假如a想和b在一起 b不想和a在一起 那么肯定不能实现愿望 就输出-1
一开始给的序列是1...n
即f[i]=i
目标序列其实有2个
1想要和l[1],r[1]在一起 可以1,l[1],......,r[1]
也可以1,r[1],.......,l[1]
可以用BFS生成这两个序列g(DFS会爆栈。。。)
然后与一开始的序列比较
因为序列是一个环
1 2 3 4 5
和
2 3 4 5 1
和
4 5 1 2 3
是等价的
所以g[i]与i是相对的
如果所有g[i]-i都大于1 那么旋转一下 所有g[i]=i
所以我们不应只认为g[i]=i是符合的
事实上 max{T[k]},(k=g[i]-i , 1<=i<=n)是符合最多的人数
只要都和下标i差同一个数 旋转这个数后 就都和下标相同了
因为c++没有负下标
所以可以 (g[i]-i+n)%n
g[i]-i+n处理负下标
%n防止出现g[i]>i时 g[i]-i+n>0的情况 因为n个人 第1个和数一圈后的第n+1个人其实是一个人
代码如下 生成p序列一开始写的dfs 7个点RE
后怕啊 多亏不是考试。。。
然后写了个比较难看的bfs生成序列
#include#include #include using namespace std;int g[50055][2];int a,b,c;int m,z=999999999;int num[250055],hash=100001;int xulie[50055];bool use[50055][2];int i;void bfs(){ int i=2,ret=0,k; xulie[1]=1; xulie[2]=g[1][0]; use[1][0]=1; if(g[g[1][0]][0]==1)use[g[1][0]][0]=1;else use[g[1][0]][1]=1; while(i<=m) { int now=xulie[i]; for(int k=0;k<=1;k++) if(!use[now][k]) { use[now][k]=1; if(g[g[now][k]][0]==now)use[g[now][k]][0]=1; else use[g[now][k]][1]=1; i++; xulie[i]=g[now][k]; } } memset(num,0,sizeof(num)); for(int a=1;a<=m;a++) { k=(xulie[a]-a+m)%m; num[k]++; ret=max(ret,num[k]); } z=min(z,(m-ret)); i=2; memset(xulie,0,sizeof(xulie));memset(use,0,sizeof(use)); xulie[1]=1; xulie[2]=g[1][1]; use[1][1]=1; if(g[g[1][1]][0]==1)use[g[1][1]][0]=1;else use[g[1][1]][1]=1; while(i<=m) { int now=xulie[i]; for(int k=0;k<=1;k++) if(!use[now][k]) { use[now][k]=1; if(g[g[now][k]][0]==now)use[g[now][k]][0]=1; else use[g[now][k]][1]=1; i++; xulie[i]=g[now][k]; } } ret=0; memset(num,0,sizeof(num)); for(int a=1;a
据说冒泡也可以做?
表示不理解 顺带求讲解
转载地址:https://blog.csdn.net/li412302070/article/details/12910575 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!