四川大学线下编程比赛第三题：书本转移

男娘i 2022-08-13 02:28 155阅读 0赞

好久没写过日志，也怪最近事情真的特别多，最近参加关于编程方面就是CSDN高校俱乐部举办的线下编程塞，说起这次编程赛，总共三道题，题目都可以在csdn高校俱乐部上看到，参加比赛的时候有点小紧张，第三题涉及到队列，当时的机器没有代码提示，坑。。。也怨自己平时写代码用惯了代码提示，很多stl的方法都是隐隐约约知道，但是具体的不知道，导致第三题没有做出来，遗憾哈！下面贴一下今天写的第三题的代码

题目 四川大学线下编程比赛第三题：书本转移

## 题目详情: ##

小强有 3 个箱子 A,B,C 用来装书，所有的书(一共n本)都按序号由小到大的顺序堆在 A上，现在他想把所有的书全都放到 C 里面去。每次他从 A 书架拿 a 本书(不够就全拿完)到 B，A 箱子翻转，然后从 B 拿 b 本书(不够就全拿完)到 C，B 箱子翻转。然后重复操作，直到所有书都到了 C，求最后的C 里面书的顺序，详细见样例。

输入描述：

输入由多组数据构成，每组数据占一行，3 个数，n(1<=n<=10^5),a(1<=a<=10^9) , b(1<=b<=10^9)，含义见题目表述。以文件结尾。

输出描述：

每组数据输出一行，首先输出数据组数，然后输出 n 个数，C 中书的排列。

## 答题说明: ##

输入样例：

4 2 1

输出样例

Case 1: 1 4 2 3

Hint

初始状态A:4321              B: 空      C:空

第一次:     A->B   A:21         B:34     C: 空

A 翻转 A:12         B:34     C: 空

B->C   A:12             B: 4     C: 3

B 翻转 A:12         B:4        C: 3

第二次:  A->B  A:空              B:214     C:3

A 翻转 A:空          B:214     C:3

B->C   A:空          B:14     C:23

B 翻转 A:空          B:41     C:23

第三次:  B->C   A:空         B:1         C:423

B 翻转  A:空         B:1         C:423

第四次:     B->C     A:空         B:空     C:1423

解析  其实当时就看出来不用什么算法，直接模拟就好，但是自己对以前的知识忘了好多，关于翻转直接标记一下即可。

#include <iostream>
    #include <queue>
    #include <algorithm>
    using namespace std;
    //A、B、C三个箱子用双端队列来表示
    deque<int> dq[3];
    //分别表示三个箱子翻转的标志，flag=0表示从front进行入队，反之从back进行入队
    int flag[3];
    int main()
    {
    	int n , a , b, T=1;
    	while(cin >> n >> a >> b)
    	{
    		//对三个双端队列和翻转标识进行初始化
    		for(int i=0;i<3;++i)
    		{
    			dq[i].clear();
    			flag[i]=0;
    		}
    		//对A双端队列进行初始化
    		for(int i=1;i<=n;++i)
    		{
    			dq[0].push_front(i);
    		}
    		while(!dq[0].empty() || !dq[1].empty())
    		{
    			//取A箱子中a本书放到B，但要分清楚是从A箱子的front处取书还是从back处取书
    			if(flag[0]==0)
    			{
    				for(int i=0;i<a&&!dq[0].empty();++i)
    				{
    					//判断B箱子的翻转情况
    					if(flag[1]==0){
    						dq[1].push_front(dq[0].front());
    					}else{
    						dq[1].push_back(dq[0].front());
    					}
    					dq[0].pop_front();
    				}
    				//从A中取完书，将A进行翻转
    				flag[0]=1;
    			}else{
    				for(int i=0;i<a&&!dq[0].empty();++i)
    				{
    					//判断B箱子的翻转情况
    					if(flag[1]==0){
    						dq[1].push_front(dq[0].back());
    					}else{
    						dq[1].push_back(dq[0].back());
    					}
    					dq[0].pop_back();
    				}
    				flag[0]=0;
    			}
    			//取B箱子中的b本书放到C中，同样要搞清楚从B的哪端进行取书
    			if(flag[1]==0)
    			{
    				for(int i=0; i<b&&!dq[1].empty();++i)
    				{
    					dq[2].push_front(dq[1].front());
    					dq[1].pop_front();
    				}
    				flag[1]=1;
    			}else{
    				for(int i=0; i<b&&!dq[1].empty();++i)
    				{
    					dq[2].push_front(dq[1].back());
    					dq[1].pop_back();
    				}
    				flag[1]=0;
    			}
    		}
    		//最后输出C箱子中的书的顺序
    		cout << "Case " << T <<": ";
    		while(!dq[2].empty())
    		{
    			cout << dq[2].front() << " ";
    			dq[2].pop_front();
    		}
    		cout << endl;
    		T++;
    	}
    	return 0;
    }