XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 5-3UVa10935 - Throwing cards away I

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 930 阅读时长 ≈ 1 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO

代码：（Accepted，0 ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//UVa10935 - Throwing cards away I
#include<iostream>
#include<queue>
int N;
int main()
{
	//freopen("in.txt", "r", stdin);
	while (scanf("%d", &N) != -1 && N != 0) {
		std::queue<int> C;
		for (int i = 1;i <= N;++i) C.push(i);
		printf("Discarded cards:");
		for (int n = 0;n < N - 1;++n) {
			if (n) printf(",");
			printf(" %d",C.front());
			C.pop();
			C.push(C.front());
			C.pop();
		}
		printf("\nRemaining card: %d\n", C.front());
	}
	return 0;
}

题意：N张扑克从1到N编号，表面那张扔掉，表面那张放最后去；表面那张扔掉，表面那张放最后去；表面那张扔掉，表面那张放最后去；表面那张扔掉，表面那张放最后去……直到只剩一张。求扔牌的顺序和最后一张。

分析：用了紫书教的queue，直接模拟，pop一张，然后把front的一张push到最后面去，再pop掉这张。直至只剩一张。 本来想直接在N张牌的数组里面，用指针p先指向第一张，把应扔掉的牌设为0，再搜索下一张不为0的牌（当p一直搜索直至指向最后一张牌的后面时，把p拉回第一张。所以其实搞个环形链表倒是不错，就是STL里我不知道list能不能做成环形的，又不高兴自己做。）。但是虽然应该快一点，实现起来比较烦，而且遇到了奇怪的bug，整了半天愣是没找出来出错的原因，鼻子都气歪了（第一次花了一下午找不出自己的错误在哪里，还是在短短的二三十行里，很不服。）。最后还是全部推倒重来，用了队列，还顺便熟悉下queue。然后发现也不会慢。