NOIP2015之篝火晚会

佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有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。

输入格式 Input Format
输入的第一行是一个整数n(3 <= n <= 50000),表示一共有n个同学。其后n行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是1的同学最希望相邻的两个同学的编号,编号是2的同学最希望相邻的两个同学的编号,……,编号是n的同学最希望相邻的两个同学的编号。
输出格式 Output Format
输出包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望,则输出-1。
样例输入 Sample Input

4
3 4
4 3
1 2
1 2

样例输出 Sample Output

2

时间限制 Time Limitation
1s

刚看这道题的时候确实有些懵,题意大概就是有一个原序列和目标序列,给你一种移动方式,求转化为目标序列的最小代价,
然后想什么dp搜索发现都不行。
然后就偷偷看了下是模拟qwq,然后就开始我奇怪的模拟猜想。
不管会不会,反正-1的分肯定是要拿的。判断不符合的方法很简单,对于两个同学a ,b,如果a想和b在相邻坐,而b却对a一点想法也没有,那么就不可能满足所有人的需求,目标序列就崩了
由于目标序列和原序列都是固定的,那么我们可以从1号同学开始,使两边满足1的需求,然后满足a两边同学的需求,最后扩展出整个目标序列,由于序列在实际上是一个环,所以从1开始时,左右是可以不分的,也就是需求两边的人在左还是在右是无所谓的
然后我们感性理解下题意会发现佳佳的命令其实可以看做将整个序列进行冒泡排序,
这时,我们就可以选择直接模拟冒泡排序,统计步数,步数就是代价。
当然50000的数据,可能需要一些优化才能过,
那么O(n)O(n)O(n)的求法就是把目标圈和原序列圈转
办法就是,用一个数组,来存每个点到它应该在的位置的距离,当几个点距离相同时,这几个点就可以一起到目标位置。所以我们可以求出最多有几个点相同距离,最终答案就是总数-相同人数。
注意的是:判断距离时依然要分两组,顺时针和逆时针都要判断一下。
方法:顺时针时,期望圈数组中第i个人,初始时应该在b[i],所以距离为(i-b[i]),为了使距离都在0~n-1之间,写为(i-b[i]+n)%n;
逆时针时,期望圈数组中第i个人,初始时应该在(n-b[i]+1)的位置【这里其实是让n作为初始圈第1个位置】同理,写为(n-b[i]+1+n)%n;

代码:

#include<bits/stdc++.h>

#define MAXN 500010

using namespace std;

int a[MAXN], b[MAXN];
int wt[MAXN][3], h[MAXN];
int n;

int ans = -1;

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d%d", &wt[i][1], &wt[i][2]);
}

// for(int i = 1; i <= n; ++i){
// printf("%d %dn", wt[i][1], wt[i][2]);
// }
h[1] = 1, h[n] = wt[1][2], h[2] = wt[1][2];

for(int i = 3; i <= n; ++i){
if(wt[h[i - 1]][1] == h[i - 2]) h[i] = wt[h[i - 1]][2];
else h[i] = wt[h[i - 1]][1];
}

// for(int i = 1; i <= n; ++i){
// printf("%d ", h[i]);
// }
// puts("");

int r, l;
for(int i = 1 ; i <= n; ++i){
r = i - 1, l = i + 1;
if(r < 1) r = n;
if(l > n) l = 1;
if((h[r] != wt[h[i]][1] || h[l] != wt[h[i]][2]) && (h[l] != wt[h[i]][1] || h[r] != wt[h[i]][2])){
puts("-1");
return 0;
}
}

for(int i = 1; i <= n; ++i){
++a[(h[i] - i + n) % n];
++b[(h[i] + i - 1) % n];
}

for(int i = 0 ; i < n; ++i){
ans = max(ans, max(a[i], b[i]));
}
printf("%dn", n - ans);
return 0;
}

本文链接:NOIP2015之篝火晚会

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:少儿编程网,谢谢!^^


*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
信息学成学科竞赛最优选择,在未来最富竞争力!
信息学成学科竞赛最优选择,在未来最富竞…
建议收藏!下半年高含金量信息学编程赛事汇总
建议收藏!下半年高含金量信息学编程赛…
信息学NOIP及CSP-J/S课程教材选用
信息学NOIP及CSP-J/S课程教材选用
想让孩子高分、保送、提升学业竞争力?NOIP了解一下!
想让孩子高分、保送、提升学业竞争力?N…
信息学竞赛考什么,竞赛流程是怎样的?
信息学竞赛考什么,竞赛流程是怎样的?
信息学奥赛怎么学,要避开其学习的几个误区
信息学奥赛怎么学,要避开其学习的几个…
JSDY 投稿者
我还没有学会写个人说明!