蓝桥ACM培训-队列

前言：

第三天的练习，今天主要与队列queue有关。

正文：

Problem:A 周末舞会-队列：

#include <bits/stdc++.h>
using namespace std;
int m,n,k,tmp1,tmp2;
queue<int>q1,q2;
int main()
{
    cin>>m>>n>>k;
    for(int i=1;i<=m;i++)
        q1.push(i);
    for(int i=1;i<=n;i++)
        q2.push(i);
    while(k--)
    {
        tmp1=q1.front();q1.pop();q1.push(tmp1);
        tmp2=q2.front();q2.pop();q2.push(tmp2);
        printf("%d %d\n",tmp1,tmp2);
    }
    return 0;
}

开两个队列即可。

Problem:B 取牌游戏-队列-SET：

#include <bits/stdc++.h>
using namespace std;
int n,k,p,num,cnt,ans[100010];
queue<int>q;
int main()
{
    cin>>n>>k>>p;
    for(int i=1;i<=k;i++)
        q.push(i);
    while(!q.empty())
    {
        num++;
        int tmp=q.front();q.pop();
        if(num%n==0)ans[cnt++]=tmp;
        for(int i=1;i<=p;i++)
        {q.push(q.front());q.pop();}
    }
    sort(ans,ans+cnt);
    for(int i=0;i<cnt;i++)
    printf("%d\n",ans[i]);
    return 0;
}

找出小明摸出的牌即可，开一个队列来模拟摸牌过程。

Problem:C 报数-队列-约瑟夫环：

#include <bits/stdc++.h>
using namespace std;
queue<int>q;
int main(){
    int n,m,tmp,cnt;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        q.push(i);
    cnt=0;
    while(q.size()>1){
        cnt++;
        tmp=q.front();q.pop();
        if(cnt%m!=0)q.push(tmp);
    }
    printf("%d\n",q.front());
    return 0;
}

同样也是队列模拟。

Problem:D 酒桌游戏-队列：

#include <bits/stdc++.h>
using namespace std;
bool judge(int x){
    if(x%7==0)return 1;
    while(x){
        if(x%10==7)return 1;
        x=x/10;
    }
    return 0;
}
struct people{
	int num;
	string name;
}pep[1009];
queue<people> q;
int main(){
	int n,m,t;
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		cin>>pep[i].name;
		pep[i].num=i;
		q.push(pep[i]);
	}
	for(int i=1;i<=m-1;i++){//调整顺序 
		q.push(q.front());q.pop();
	}
	while(q.size()>1){
		people tmp=q.front();q.pop();
		if(!judge(t))q.push(tmp);
		t++;
	}
	cout<<q.front().name<<endl;
	return 0;
}

和上一题相似，只不过这一题需要使用结构体来进行排序，同时写一个判断是否出局的函数会方便很多。

Problem:E 海港-队列：

#include<bits/stdc++.h>
using namespace std;
int nation[1000009];
struct people{
	int t,x;//来的时间和国籍 
};
queue<people> pep;
people tmp;
int main(){
	int n,t,m,x,ans=0;cin>>n;
	 for(int i=1;i<=n;i++){
	 	cin>>t>>m;
	 	while(!pep.empty()){//检验时间并修正答案 
	 		tmp=pep.front();
	 		if(tmp.t+86400<=t){
	 			nation[tmp.x]--;
	 			if(nation[tmp.x]==0)ans--;
	 			pep.pop();
	 			continue;
			}
			break;//一艘船上的人时间相同 
		}
		for(int o=1;o<=m;o++){//先全部储入 
		 	cin>>x;
		 	tmp.x=x;tmp.t=t;
		 	pep.push(tmp);
		 	nation[x]++;
		 	if(nation[x]==1)ans++;
		}
		cout<<ans<<endl;
	}
}

这道题想了很久，发现船的批次根本没用，我们只需要建立一个结构体包含一个人的到达时间和国籍即可，按输入顺序先把第一批次的人依次储入队列中，再根据下一组的时间更新答案和队列，依次输出即可。