本文主要是介绍队列思想的题目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P1540 [NOIP2010 提高组] 机器翻译
#include <bits/stdc++.h>
using namespace std;
int n, m, x, ans;
bool vis[1006];
queue<int> q;
int main()
{scanf("%d %d", &m, &n); //内存容量和文章长度while(n--){scanf("%d", &x);if(!vis[x]){ //不在内存中 ans++; //答案++ q.push(x); //放入内存 vis[x]=true; //表示在内存中 if(q.size()>m){ //如果放入后超了内存 vis[q.front()]=false; //队首元素出队 q.pop(); //队首元素出队}}} printf("%d", ans);return 0;
} P2058 [NOIP2016 普及组] 海港
使用map存，70分暴力
#include <bits/stdc++.h>
using namespace std;
int n, x, flag, t[100010], k[100010], ans[100010];
bool vis[100010]; //vis[i]为false表示国籍为i的人没上船
map<int, int> a[100010]; //a[i][j]=k 表示第i艘船上第j个人的国籍是k
int main()
{scanf("%d", &n);//3*10^5for(int i=1; i<=n; ++i){ //n艘船 scanf("%d %d", &t[i], &k[i]); //第i艘船到达的时间、船上的乘客数for(int j=1; j<=k[i]; ++j){ //输入每个乘客的国籍 scanf("%d", &x); //国籍 a[i][j]=x; } }for(int i=1; i<=n; ++i){ //n艘船 //以每一艘船到达时间为止的24小时(2424小时=86400秒）内//所有乘船到达的乘客来自多少个不同的国家//找到时间内的船, 记为flag memset(vis, 0, sizeof(vis));for(int j=1; j<=i; ++j){if(t[j]+86400>t[i]){flag=j;break;}} //从第flag艘船到第i艘船开始计算for(int j=flag; j<=i; ++j){for(int kk=1; kk<=k[j]; ++kk){if(!vis[a[j][kk]]){ans[i]++; vis[a[j][kk]]=true; }}} printf("%d\n", ans[i]);}return 0;
} 使用队列存乘客，100分
#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
int cnt[100010]; //cnt[i]表示船上有几个国籍为i的人
struct node //乘客
{int tim; //乘客到达的时间 int nation; //乘客的国籍
}a;
queue<node> q;
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){ //n艘船 scanf("%d %d", &a.tim, &k); //第i艘船到达的时间、船上的乘客数while(k--){scanf("%d", &a.nation); //乘客的国籍 if(cnt[a.nation]==0){ //如果是新的国籍, 答案+1 ans++; //国籍种类加一 }cnt[a.nation]++; //累计该国籍的人数 q.push(a); //乘客入队 }while(!q.empty() && q.front().tim+86400<=a.tim){ //枚举乘客 //如果队首乘客上船时间超了24小时 //乘客的国籍数减一 cnt[q.front().nation]--;//如果这个国籍没人了, 答案减一 if(cnt[q.front().nation]==0){ans--;}//该乘客出队 q.pop();}//输出答案 printf("%d\n", ans); }return 0;
} 这篇关于队列思想的题目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
