7-1 银行业务队列简单模拟 (30 分)

设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时,B窗口处理完1个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。

输入格式:

输入为一行正整数,其中第1个数字N(≤1000)为顾客总数,后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务,为偶数的顾客则去B窗口。数字间以空格分隔。

输出格式:

按业务处理完成的顺序输出顾客的编号。数字间以空格分隔,但最后一个编号后不能有多余的空格。

输入样例:

8 2 1 3 9 4 11 13 15

输出样例:

1 3 2 9 11 4 13 15

解题思路:这道题的意思就是模拟队列,将偶数的数字存到b窗口,将奇数的数字存到a窗口,而且是先进先出,所以可以采用队列,将偶数的放在b队列,将奇数的放在a队列;然后每输出两个a队列中的元素
再输出一个b队列中的元素;
还有注意的一个点就是,最后是a队列中的元素结尾还是b队列中的元素结尾,这个要分情况讨论;主要是最后空格的规范问题;
解法一:模拟队列
代码如下:
  1 #include<iostream>
  2 using namespace std;
  3 
  4 
  5 
  6 struct queue{
  7     int data[1005];      //用于存队列的数据; 
  8     int tail;            //用来记录从尾部插入了多少个元素; 
  9     int head;            //计数队头,方便取出队头的元素; 
 10 };
 11 
 12 void push(queue *q ,int  tmp )       //实现队列的push用法;传入类型为 queue 的指针 q;传入要入队的数tmp; 
 13 {
 14     q->tail ++;                      //每入队一个元素,尾部计数器+1; 
 15     q->data[q->tail] = tmp;          //将元素入队; 
 16 }
 17 
 18 int pop(queue *q)                    //取出队列的数字,从前端取出;此时要利用head记数; 
 19 {
 20     q->head++;                     //每取一个,就将head+1,记数; 
 21     return q->data[q->head];        //返回队头的元素;  
 22 } 
 23 
 24 void init(queue *q)                   //初始化; 
 25 {
 26     q->tail = -1 ;                     //将尾和头记数均初始化为-1; 
 27     q->head = -1;
 28 }
 29 
 30 int notEmpty(queue *q)                     //判断队列是否为空; 
 31 {
 32     int i ;
 33     if(q->tail == q->head)              //如果尾和头的记数一样,则队列为空; 
 34     {
 35         i = 0;    
 36     }
 37     else
 38     i = 1;
 39     return i;                           //判断队列不为空; 
 40 }
 41 int counta = 0,countb = 0;               //用counta 记录入a队列的个数;用countb  记录入b队列的个数; 
 42 int main()
 43 {
 44     queue a ;          //定义,实例化a; 
 45     queue b;           //定义,实例化b; 
 46     init(&a);            //初始化a队列,并要用引用符号; 
 47     init(&b);           //初始化b队列,并用引用符号; 
 48     int n ;
 49     int c;
 50     cin>>n;
 51     for(int i = 0 ; i < n ; i++)
 52     {
 53         cin>>c;
 54         if(c%2==0)
 55         {
 56             push(&b,c);              //如果是偶数,则进b队列; 
 57             countb++;             //countb相应+1; 
 58         }
 59         else
 60         {
 61             push(&a,c);           //如果是奇数,则进a队列; 
 62             counta++;             //counta相应+1; 
 63         }
 64 
 65     }
 66       //分情况,注意最后到底是a队列的数结尾还是b队列的数结尾,这影响格式; 
 67     if(counta > countb *2)                //counta大于两倍countb,是a队列的元素结尾,则a最后一个元素后面不能加空格; 
 68     {
 69             while(notEmpty(&a)||notEmpty(&b))        //当a队列不空或者b队列不空时; 
 70         {
 71             if(notEmpty(&a))                    //a队列不空; 
 72             {
 73                cout<<pop(&a);                 
 74                counta--; 
 75                if(counta != 0)
 76                cout<<" "; 
 77                cout<<pop(&a);                  //输出两个a队列的元素; 注意这里a最后一个元素后面不能加空格; 
 78                counta--;
 79                if(counta != 0)
 80                cout<<" ";    
 81             }
 82             if(notEmpty(&b))
 83             {
 84                 cout<<pop(&b);                //输出一个b队列的元素; 
 85                 cout<<" ";
 86             }
 87         }
 88     }
 89     else
 90     if(counta <= countb *2)             //counta小于等于两倍countb,是b队列的元素结尾,则b最后一个元素后面不能加空格; 
 91     {
 92             while(notEmpty(&a)||notEmpty(&b))
 93         {
 94             if(notEmpty(&a))
 95             {
 96                cout<<pop(&a);           //输出两个a队列的元素; 
 97                cout<<" ";
 98                cout<<pop(&a);
 99                cout<<" ";    
100             }
101             if(notEmpty(&b))
102             {
103                 cout<<pop(&b);           //输出一个b队列的元素,注意b队列最后一个元素的后面不能加空格; 
104                 countb--;
105                 if(countb != 0) 
106                 {
107                      cout<<" ";
108                 }
109 
110             }
111         }
112     }
113     
114     
115     
116     return 0;
117 }

解法二:直接用stl中的queue;

 1 #include<iostream>
 2 #include<queue>              //队列头文件 
 3 using namespace std;
 4 
 5 
 6 long long int b[10005]; 
 7 queue<int>qa;        //定义一个qa队列,用于存放奇数 
 8 queue<int>qb;        //定义一个qb队列,用于存放偶数; 
 9 int tmp1;             //用于取出qa“每次最前” 的元素; 
10 int tmp2;             //用于取出qa“每次最前” 的元素; 
11 int n ;                
12 int main()
13 {
14     cin>>n;
15     for(int i = 0 ; i < n ; i++)
16     {
17         cin>>b[i];
18         if(b[i]%2==0)    
19         qb.push(b[i]);     //如果为偶数,则放入qb队列; 
20         else 
21         qa.push(b[i]);      //如果为奇数,则放入qa队列; 
22     }
23 
24     int counta = qa.size();        //用counta 记录qa队列的长度; 
25     int countb = qb.size();       //用countb  记录qb队列的长度; 
26      //分情况,注意最后到底是qa队列的数结尾还是qb队列的数结尾,这影响格式;
27     if(counta > countb *2)                            //counta大于两倍countb,是qa队列的元素结尾,则a最后一个元素后面不能加空格;
28     {
29             while(!qa.empty()||!qb.empty())      //当qa队列不空或者qb队列不空时;
30         {
31             if(!qa.empty())              //a队列不空;  
32             {
33                tmp1 = qa.front();        //取出qa 队头的元素; 
34                cout<<tmp1;              //输出qa队头的元素; 
35                qa.pop();                 //将qa队头的元素去掉; 
36                counta--;               //qa长度-1; 
37                if(counta != 0)         //注意这里a最后一个元素后面不能加空格; 
38                cout<<" ";     
39                tmp1 = qa.front();          //再进行一遍上面的操作; 
40                cout<<tmp1;
41                qa.pop();
42                counta--;
43                if(counta != 0)
44                cout<<" ";    
45             }
46             if(!qb.empty())
47             {
48                 tmp2 = qb.front();          //取出qb 队头的元素;
49                 cout<<tmp2;                  //输出qb队头的元素; 
50                 qb.pop();                     //将qb队头的元素去掉; 
51                 cout<<" ";
52             }
53         }
54     }
55     else
56     if(counta <= countb *2)                         //counta小于等于两倍countb,是b队列的元素结尾,则b最后一个元素后面不能加空格; 
57     {
58             while(!qa.empty()||!qb.empty())             //当qa队列不空或者qb队列不空时; 
59         {
60             if(!qa.empty())                     //qa队列不空时; 
61             {
62                tmp1 = qa.front();           //与上面的if类似,只是不需要注意尾部是否输出空格; 
63                cout<<tmp1;        
64                qa.pop();
65                cout<<" ";
66                tmp1 = qa.front();
67                cout<<tmp1;
68                qa.pop();
69                cout<<" ";    
70             }
71             if(!qb.empty())
72             {
73                 tmp2 = qb.front();          //与上面的if类似,需要注意尾部是否输出空格; 
74                 cout<<tmp2;
75                 qb.pop();
76                 countb--;
77                 if(countb != 0)
78                 {
79                      cout<<" ";
80                 }
81 
82             }
83         }
84     }
85 
86     
87     return 0;
88 }

 

上一篇:把本地文件系统以nfs形式远程挂载


下一篇:1年小白总结--测试流程