讨论 / 提醒
怡红公子 2012-10-19 06:44:00
点我顶贴 收藏 删除
原来b1,b2.....可以不相邻
#1 怡红公子@2012-01-17 10:04:00
回复 删除
而且b1,b2....并不严格递增

篝火晚会

首先把这个圈看做一个图,每个同学看做一个顶点。因为要形成环,所以每个顶点的度必须为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就是调换次数最小的。

#2 谧芒@2012-10-19 06:44:00
回复 删除
这题目真过分

题目描述一点都不清楚,坑爹啊,按他的描述样例都不对

#3 不争不羁绊@2016-01-03 13:07:23
回复 删除
回复 #2 谧芒:讲得好
#4 Heartbeat@2016-02-17 14:02:03
回复 删除
回复 #3 不争不羁绊:样例是可以的,m=1的时候交换两次
查看更多回复
提交回复