| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 563 人关注过本帖
标题:问一道题:
只看楼主 加入收藏
akadi
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2006-5-11
收藏
 问题点数:0 回复次数:3 
问一道题:

篝火晚会

(fire.pas/c/cpp)

【问题描述】

佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有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。我们需要佳佳用最少的总代价实现同学们的意愿,你能帮助佳佳吗?

【输入文件】

输入文件fire.in的第一行是一个整数n(3 <= n <= 50000),表示一共有n个同学。其后n行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是1的同学最希望相邻的两个同学的编号,编号是2的同学最希望相邻的两个同学的编号,……,编号是n的同学最希望相邻的两个同学的编号。

【输出文件】

输出文件fire.out包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望,则输出-1。

【样例输入】

4

3 4

4 3

1 2

1 2

【样例输出】

2

【数据规模】

对于30%的数据,n <= 1000;

对于全部的数据,n <= 50000。

搜索更多相关主题的帖子: center 佳佳 高中 如何 
2006-05-13 20:43
akadi
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2006-5-11
收藏
得分:0 
提供个思路就好,在线等
2006-05-13 20:44
gaga
Rank: 1
等 级:新手上路
威 望:2
帖 子:307
专家分:0
注 册:2006-4-5
收藏
得分:0 

你也发这么多啊
C那都有了


明天的明天还有明天。 可是今天却只有一个。 public Copy from 无缘今生
2006-05-13 21:28
akadi
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2006-5-11
收藏
得分:0 
就发两个嘛,那边算误发的,本来不知道这个坛子~~
2006-05-13 21:36
快速回复:问一道题:
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031413 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved