[蓝桥杯-历届试题] 拉马车 (栈与队列)

最新推荐文章于 2022-04-04 12:19:00 发布

Skyed.blue

最新推荐文章于 2022-04-04 12:19:00 发布

阅读量741

点赞数

分类专栏：蓝桥杯算法数据结构

本文链接：https://blog.csdn.net/Skyed_blue/article/details/96616414

版权

问题描述
　　小的时候，你玩过纸牌游戏吗？
　　有一种叫做“拉马车”的游戏，规则很简单，却很吸引小朋友。

其规则简述如下：
　　假设参加游戏的小朋友是A和B，游戏开始的时候，他们得到的随机的纸牌序列如下：
　　A方：[K, 8, X, K, A, 2, A, 9, 5, A]
　　B方：[2, 7, K, 5, J, 5, Q, 6, K, 4]

其中的X表示“10”，我们忽略了纸牌的花色。

从A方开始，A、B双方轮流出牌。

当轮到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。

此例中，游戏过程：
　　A出K，B出2，A出8，B出7，A出X，此时桌上的序列为：

K,2,8,7,X

当轮到B出牌时，他的牌K与桌上的纸牌序列中的K相同，则把包括K在内的以及两个K之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。
　　此时，A、B双方的手里牌为：
　　A方：[K, A, 2, A, 9, 5, A]
　　B方：[5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]

赢牌的一方继续出牌。也就是B接着出5，A出K，B出J，A出A，B出5，又赢牌了。
　　5,K,J,A,5
　　此时双方手里牌：
　　A方：[2, A, 9, 5, A]
　　B方：[Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]

注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。

当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。

对于本例的初始手牌情况下，最后A会输掉，而B最后的手里牌为：

9K2A62KAX58K57KJ5

本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出-1。

输入为2行，2个串，分别表示A、B双方初始手里的牌序列。
　　输出为1行，1个串，表示A先出牌，最后赢的一方手里的牌序。
样例输入
96J5A898QA
6278A7Q973
样例输出
2J9A7QA6Q6889977
样例输入
25663K6X7448
J88A5KJXX45A
样例输出
6KAJ458KXAX885XJ645
数据规模和约定
　　我们约定，输入的串的长度不超过30

资源约定：
　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：
　　main函数需要返回0;
　　只使用ANSI C/ANSI C++ 标准;
　　不要调用依赖于编译环境或操作系统的特殊函数。
　　所有依赖的函数必须明确地在源文件中 #include
　　不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

思路分析：

明显的栈与队列数据结构。牌面为栈，A,B为队列，接下来模拟拉马车过程。
1.将A, B初始牌入队。
2.A出队(出牌)，将A的出队元素压进牌面。
3.检索牌面是否有与A出的牌相同，若有，则将这一段牌反向入A队同时牌面出栈，并且A再次出牌……
4.A出牌后若判断A队列为空，则判B赢牌。
B同理。

牌面不能用STL里的stack，因为stack是容器适配器，无法遍历，因此就无法进行检索过程。
这道题主要难在要处理的内容和细节太多，而且某一处地方不对，结果就不对，debug比较困难。另外，这道题的所有测试数据都有结果，-1不用判定也可以
下面一个代码是大一寒假做的，当时还不会用STL，手写链队，将细节全盘打印出来（因为要debug…）

#include <cstdio>
#include <algorithm>
using namespace std;

typedef struct node
{
   
	char data;
	struct node *next;
}Queue;

void create(Queue *&L, Queue *&r)	//创建队列并传递尾指针 
{
   
	char ch;
	L = (Queue *)malloc(sizeof(Queue));
	r = L;
	while((ch = getchar()) != '\n')
	{
   
		Queue *s = (Queue *)malloc(sizeof(Queue));
		s->data = ch;
		r->next = s;
		r = s;
	}
	r->next = NULL;
}

void print(Queue *&L)	//输出队列 
{
   
	Queue *p;
	p = L->next;
	while(p != NULL)
	{
   
		printf("%c",p->data);
		p = p->next;
	}
	printf("\n");
}

int main()
{
   
	int i, j, ok1 = 1, ok2 = 1;	//用ok1和ok2判定赢牌后先出牌 
	char a[100]

最低0.47元/天解锁文章