C++知识点总结(57)：STL综合

一、数据结构

1. 队列

功能	代码
定义	queue<tp>q
入队	.push(x)
出队	.pop()
队头	.front()
队尾	.back()
为空	.empty()
大小	.size()

2. 映射

功能	代码
定义	map<tp1,tp2>name
增/改	mp[key]=value
删除	.erase(key)
全删	.clear()
头部	.begin()
尾部	.end()
key 出现	.count(key)
为空	.empty()
大小	.size()
查找	.find(key)
键	it->first
值	it->second

二、队列例题

1. 约瑟夫环（数据加强）

题目描述

$n$ 个人报数，报到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，以此类推，输出依次出圈人的编号。

输入描述

一行两个整数$n,m$。

输出描述

一行 $n$ 个整数，相邻整数用一个空格隔开，按顺序输出每个出圈人的编号

样例1

输入

10 3

输出

3 6 9 2 7 1 8 5 10 4

提示

对于 $50\%$ 的数据，$n,m\le 50$
对于 $80\%$ 的数据，$n\le 1000,m\le 10^6$
对于 $100\%$ 的数据，$1\le n\le 5000,1\le m\le 10^9$

程序1: 暴力

#include<bits/stdc++.h>
using namespace std;
int n,m;
queue<int>q;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)q.push(i);for(int i=1;i<=n;i++){//一共有n个人需要出圈for(int j=1;j<=m-1;j++){//前1~m-1的人不用出圈q.push(q.front());//备份一份本体到队尾q.pop();//本体删除}cout<<q.front()<<" ";//输出出圈人q.pop();//出圈人出圈}return 0;
}

问题：直接模拟会非常耗时，尤其是 $m>n$ 的时候，可以考虑使用模运算作答。

参考答案

#include<bits/stdc++.h>
using namespace std;
int n,m;
queue<int>q;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)q.push(i);for(int i=1;i<=n;i++){for(int j=1;j<=(m-1)%q.size();j++){//模运算，记得不要直接m%=nq.push(q.front());q.pop();}cout<<q.front()<<" ";q.pop();}return 0;
}

2. 打印队列

题目描述

学生会里只有一台打印机，但是有很多文件需要打印，因此打印任务不可避免地需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个 $1\sim 9$ 间的优先级，优先级越高表示任务越急。
打印机的运作方式如下：首先从打印队列里取出一个任务 $J$，如果队列里有比 $J$ 更急的任务，则直接把 $J$ 放到打印队列尾部，否则打印任务 $J$（此时不会把它放回打印队列）。
给定打印队列中各个任务的优先级，以及所关注的任务在队列中的位置（队首位置为 $0$），求该任务完成的时刻。所有任务都需要 $1$ 分钟打印。
例如，打印队列为 { 1 , 1 , 9 , 1 , 1 , 1 } \{ 1,1,9,1,1,1 \} {1,1,9,1,1,1}，目前处于队首的任务最终完成时刻为 $5$。

输入描述

多组数据，第一行一个整数 $T$，表示了有 $T$ 组数据。
每组数据，第一行两个整数 $n,m$，分别表示队列中任务数量，以及所关注任务的位置。
接下来一行 $n$ 个数，分别表示 $n$ 个任务的优先级。

输出描述

每组数据输出一行，表示所关注任务的完成时刻。

样例1

输入

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

输出

1
2
5

提示

对于 $20\%$ 的数据，$0\le m<n\le 10$。
对于 $60\%$ 的数据，$0\le m<n\le 100$。
对于 $100\%$ 的数据，$T\le 10,0\le m<n\le 1000$。

参考答案

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int cnt[10];
struct task{int id,prio;//编号和优先级
};
bool check(int p){//查找打印优先级for(int i=p+1;i<=9;i++)//遍历更高的优先级if(cnt[i]!=0)//有更高优先级的任务等待打印return true;//不打印return false;//打印
}
void solve(){memset(cnt,0,sizeof(cnt));//清空优先级计数queue<task>q;cin>>n>>m;for(int i=0,p;i<n;i++){//id从0开始cin>>p;//输入优先级cnt[p]++;//增加对应优先级任务的计数q.push({i,p});//存储任务}int ans=0;while(!q.empty()){auto[id,p]=q.front();//取出队首q.pop();if(check(p))//不可以打印q.push({id,p});else{ans++;//增加做任务的次数cnt[p]--;//减少对应优先级任务的计数if(id==m){//是否为关注任务cout<<ans<<endl;return;}}}
}
int main(){cin>>t;while(t--)solve();return 0;
}

3. 小组队列

题目描述

有 $m$ 个小组，$n$ 个元素，每个元素属于且仅属于一个小组。
支持以下操作：

• push x：使元素 $x$ 进队，如果前边有 $x$ 所属小组的元素，$x$ 会排到自己小组最后一个元素的下一个位置，否则 $x$ 排到整个队列最后的位置。
• pop：出队，弹出队头并输出出队元素，出队的方式和普通队列相同，即排在前边的元素先出队。

输入描述

第一行有两个正整数 $n,m$，分别表示元素个数和小组个数，元素和小组均从 $0$ 开始编号。
接下来一行 $n$ 个非负整数 $A_i$ ，表示元素 $i$ 所在的小组。
接下来一行一个正整数 $T$，表示操作数。
接下来 $T$ 行，每行为一个操作。

输出描述

对于每个出队操作输出一行，为出队的元素。

样例1

输入

4 2
0 0 1 1
6
push 2
push 0
push 3
pop
pop
pop

输出

2
3
0

提示

对于 $30\%$ 的数据，$1\le n\le 100,1\le m\le 10,T\le 50$。
对于 $100\%$ 的数据，$1\le n\le 10^5,1\le m\le 300,T\le 10^5$，输入保证操作合法。

参考答案

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int a[100010];//每个人所属的队伍编号
queue<int>q;//队伍编号
queue<int>team[305];//队伍成员的队列数组
int main(){cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];cin>>t;while(t--){string op;cin>>op;if(op=="push"){int x;cin>>x;if(team[a[x]].empty())//如果x所属队伍之前没有人入队q.push(a[x]);//将x所属队伍入队team[a[x]].push(x);//将x入队到对应队伍中} else {int x=q.front();//取出下一个要出队的队伍编号cout<<team[x].front()<<endl;//输出当前队首队伍中的第一个人的编号team[x].pop();//将当前队首队伍中的第一个人出队if(team[x].empty())//如果当前队首队伍中没有人了q.pop();//将当前队伍从队伍中删除}}return 0;
}

4. 日志统计 2.0

题目描述

小猴维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有 $N$ 行。其中每一行的格式是 ts id，表示在 $\mathtt{ts}$ 时刻编号 $\mathtt{id}$ 的帖子收到一个"赞"。
现在小猴想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 $D$ 的时间段内收到不少于 $K$ 个赞，小猴就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻 $T$ 满足该帖在 $[T,T+D)$ 这段时间内（注意是左闭右开区间）收到不少于 $K$ 个赞，该帖就曾是"热帖"。
除此之外，小猴还想知道哪个长度为 $D$ 的时间段内的"热帖"种类最多，小猴称这个段时间为"黄金时间段"。这里统计帖子的出现次数只能使用该黄金时间段内的帖子，也就是说在黄金时间段内的帖子之前可能是"热帖"，但是仅在黄金时间段内却可能不是"热帖"。
例如，$N=5,D=3,K=2$，$N$ 个帖子依次是 { 1 , 1 } , { 2 , 1 } , { 3 , 2 } , { 4 , 2 } , { 5 , 3 } \{1,1\},\{2,1\},\{3,2\},\{4,2\},\{5,3\} {1,1},{2,1},{3,2},{4,2},{5,3}（以 { t s , i d } \{\tt ts,id\} {ts,id} 的形式依次给出每个帖子的信息），那么在黄金时间段 $[2,4]$ 内“热帖”的个数只有 $1$ 个，其中编号为 $1$ 的帖子在时间 $[2,4]$ 中只出现了一次，虽然它曾经是"热帖"。
给定日志，请你帮助小猴统计出"黄金时间段"内的"热帖"种类数，以及输出所有曾是"热帖"的帖子编号。

输入描述

第一行包含三个整数 $N,D,K$。
以下 $N$ 行每行一条日志，包含两个整数 $\mathtt{ts},\mathtt{id}$。

输出描述

输出两行：
第一行，表示"黄金时间段"内的帖子种类数。
第二行，按从小到大的顺序输出热帖 $\mathtt{id}$。每个 $\mathtt{id}$ 之间空格隔开, 如果没有任何热帖就输出 −1。

样例1

输入

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出

1
1 3

样例2

输入

7 10 1
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出

2
1 3 10 

样例3

输入

7 10 3
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出

0
-1

提示

对于 $50\%$ 的数据，$1\le K\le N\le 1000$。
对于 $100\%$ 的数据，$1\le K\le N\le 2\times 10^5,0\le \mathtt{id},\mathtt{ts}$ $\le 10^5$。

参考程序

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int n,d,k,cnt;
int sum[MAXN];
int isHot[MAXN];
struct LOG{int ts,id;bool operator<(const LOG&rhs)const{return ts<rhs.ts;}
}logs[MAXN];
queue<LOG>q;//某个长度为D的时间段的热搜情况
int main(){cin>>n>>d>>k;for(int i=1;i<=n;i++)cin>>logs[i].ts>>logs[i].id;sort(logs+1,logs+n+1);int ans=0;for(int i=1;i<=n;i++){while(!q.empty()&&q.front().ts<=logs[i].ts-d){if(sum[q.front().id]==k)//点赞个数刚好是k条cnt--;//减少热帖个数sum[q.front().id]--;q.pop();}//把当前记录放入日志q.push(logs[i]);sum[logs[i].id]++;if(sum[logs[i].id]==k){cnt++;//新增一个热帖isHot[logs[i].id]=1;//标记为热帖}ans=max(ans,cnt);}cout<<ans<<endl;if(ans==0)cout<<"-1\n";else{for(int i=1;i<=n;i++)if(isHot[i])cout<<i<<" ";}return 0;
}

三、映射真题

1. 眼红的 Medusa

题目描述

虽然 Miss Medusa 到了北京，领了科技创新奖，但是她还是觉得不满意。原因是：他发现很多人都和她一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。

输入格式

第一行两个整数 $n,m$，表示有 $n$ 个人获得科技创新奖，$m$ 个人获得特殊贡献奖。
第二行 $n$ 个正整数，表示获得科技创新奖的人的编号。
第三行 $m$ 个正整数，表示获得特殊贡献奖的人的编号。

输出格式

输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。

样例1

输入

4 3
2 15 6 8
8 9 2

输出

2 8

提示

对于 $60\%$ 的数据，$0\le n,m\le 1000$，获得奖项的人的编号 $<2\times 10^9$；
对于 $100\%$ 的数据，$0\le n,m\le 10^5$，获得奖项的人的编号 $<2\times 10^9$。
输入数据保证第二行任意两个数不同，第三行任意两个数不同。

参考答案

#include<bits/stdc++.h>
using namespace std;
map<int,bool>mp;
int n,m,awd[100010];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>awd[i];for(int i=1,id;i<=m;i++)cin>>id,mp[id]=true;for(int i=1;i<=n;i++)if(mp[awd[i]]==true)cout<<awd[i]<<" ";return 0;
}

2. 美食评委

题目描述

一年一度的美食比赛火热进行中，小猴作为评委需要对一些选手的菜品打分，所有菜品从左到右排成一排，编号依次为 $1\sim n$，第 $i$ 个菜品的美味值是 $d_i$。小猴可以自己选择对那些选手的菜品进行打分，但是必须满足以下两个条件：

• 至少选择两位选手的菜品；
• 选择的第一个选手和最后一位选手的菜品美味值必须相同。

小猴所选的第一个菜品和最后一个菜品之间（不包含第一个和最后一个菜品）的部分菜品可以选择不要，请你帮助小猴计算所选菜品美味值的总和的最大值是多少？

输入描述

第一行一个整数 $n$；
第二行 $n$ 个整数 $d_i$。

输出描述

一行一个整数，表示所选菜品美味值的总和的最大值。

样例1

输入

5
1 2 3 1 2

输出

8

样例2

输入

5
100 1 1 -3 1

输出

3

提示

对 $40\%$ 的数据保证：$2\le n\le 5000,d_i>0$；
对 $100\%$ 的数据保证：$2\le n\le 2\times 10^5,-10^9\le d_i\le 10^9$。