当前位置:首页 > 模拟 > 正文
CAIOJ1609【链表】又是洗牌问题
1937+

题目大意:按照一定规则进行洗牌,即第一张扔掉,原偶数位置依次放到后面,这样一直下去,扔掉的牌依次是什么?

【题目描述】

桌上有一叠牌,从第一张牌(即位于顶面的牌)开始从上往下依次写上数字1~n。不断进行洗牌操作,每次洗牌操作如下:假如剩下k(k>=2),把第一张牌扔掉,然后从最上面那张牌往下算起,剩下的牌中抽出位置为奇数的牌,依次放到最后。

假如k为偶数,即序列为:2,4,6,8……k-2,k, 1,3,5,7,……k-3,k-1

假如k为奇数,即序列为:2,4,6,8……k-3,k-1,1,3,5,7,……k-2,k

求依次扔掉的牌的数字顺序是?

比如k=6

第1张:1 2 3 4 5 6(扔掉的是1)

第2张:3 5 2 4 6 (扔掉的是3)

第3张:2 6 5 4 (扔掉的是2)

第4张:5 6 4 (扔掉的是5)

第5张:4 6 (扔掉的是4)

第5张:6 (扔掉的是6)

所以序列是:1 3 2 5 4 6

【输入格式】

一个正整数k (k 大于2,小于等于10000)

【输出格式】

输出扔掉的序列,相邻两个用一个空格隔开。

【样例输入】

6

【样例输出】

1 3 2 5 4 6

解题思路

哇,好像找到一道链表的题目,如果直接用数组(1个),逐个移动一定超时!但细想一下,不用链表反而更快,因为链表修改指针的值也是双倍时间的。我们其实可以运用归并排序的思想,扔掉一个数之后,将奇数编号的数和偶数编号的数合并到一起。为了避免放到b后再放回a那么麻烦,我们可以(从0开始)偶数次扔牌时用a的数据,产生新的数据放到b;奇数次扔牌用b的数据,产生新的数据放到a。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

CAIOJ1609【链表】又是洗牌问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!