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

🕗 发布于 2024-11-17 07:50 c++ java 算法

STL综合

一、数据结构
- 1. 队列
- 2. 映射
二、队列例题
三、映射真题
- 1. 眼红的 Medusa
- 2. 美食评委

一、数据结构

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\le1000,m\le10^6$
对于 $100\%$ 的数据， $1\le n\le5000,1\le m\le10^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%=n
            q.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 \}$ ，目前处于队首的任务最终完成时刻为 $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 \leq m < n \leq 10$ 。
对于 $60\%$ 的数据， $0 \leq m < n \leq 100$ 。
对于 $100\%$ 的数据， $T \leq 10, 0 \leq m < n \leq 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 \leq n \leq 100, 1 \leq m \leq 10, T \leq 50$ 。
对于 $100\%$ 的数据， $1≤n≤10^5,1≤m≤300,T≤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，表示在 $\tt ts$ 时刻编号 $\tt 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\}$ （以 $\{\tt ts,id\}$ 的形式依次给出每个帖子的信息），那么在黄金时间段 $[2, 4]$ 内“热帖”的个数只有 $1$ 个，其中编号为 $1$ 的帖子在时间 $[2, 4]$ 中只出现了一次，虽然它曾经是"热帖"。
给定日志，请你帮助小猴统计出"黄金时间段"内的"热帖"种类数，以及输出所有曾是"热帖"的帖子编号。

输入描述

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

输出描述

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

样例1

输入

输出

1
1 3

样例2

输入

输出

2
1 3 10

样例3

输入

输出

0
-1

提示

对于 $50\%$ 的数据， $1 \leq K \leq N \leq 1000$ 。
对于 $100\%$ 的数据， $1≤K≤N≤2×10^5,0≤\tt{id,ts}$ $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\%$ 的数据， $\leq n, m \leq 1000$ ，获得奖项的人的编号 $\lt 2 \times 10^9$ ；
对于 $100\%$ 的数据， $\leq n, m \leq 10^5$ ，获得奖项的人的编号 $\lt 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≤n≤5000,d_i>0$ ；
对 $100\%$ 的数据保证： $2≤n≤2×10^5,-10^9\le d_i\le10^9$ 。

原文地址：https://blog.csdn.net/joe_g12345/article/details/143820692

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：基于迭代重加权最小二乘法的算法及例程
下一篇：大数据-226 离线数仓 - Flume 优化配置自定义拦截器拦截原理了拦截器实现 Java

Java学习，基本数据类型
System.out.println("最小值：Double.MIN_VALUE=" + Double.MIN_VALUE);System.out.println("最小
阅读更多2024-11-17
创建第一个react项目
通过以上步骤，你已经成功创建并运行了你的第一个React项目。接下来，你可以继续探索React的更多功能，编写更复杂的组件和应用程序。希望这个教程对你有所帮助！如果有任何问题，欢迎随时提问。参考资料R
阅读更多2024-11-17
从零开始的c++之旅——二叉搜索树
这与之前实现的二叉树类似，只不过用上了模板跟构造函数，因为构造函数我们在后面需要用来生成节点。K _key;:_key(key){}//这里也能体现封装思想，不管我们如何实现的类此处我们只需定义成No
阅读更多2024-11-17
c/c++内存管理
int main()// new/delete 和 malloc/free最大区别是 new/delete对于【自定义类型】除了开空间还会调用构造函数和析构函数free(p1);delete p2;/
阅读更多2024-11-17
1、PyTorch介绍与张量的创建
【代码】1、PyTorch介绍与张量的创建。
阅读更多2024-11-17
‌REST风格（Representational State Transfer）
REST风格的核心思想是将Web应用程序的功能作为资源来表示，使用统一的标识符（URI）来对这些资源进行操作，并通过HTTP协议（如GET、POST、PUT、DELETE等）来定义对这些资源的操作。‌
阅读更多2024-11-17
软件测试 —— 自动化基础
自动化是指自动的代替人的行为完成操作，自动化在生活中可以说是随处可见，如：自动洒水机、自动洗手液等，这些生活中的自动案例有效的减少了我们人力的消耗，同时也提高了我们的生活质量，在我们软件中的自动化测试
阅读更多2024-11-17
Python爬虫下载新闻，Flask展现新闻（2）
Python爬虫下载新闻和Flask展现新闻的主要技术
阅读更多2024-11-17
【CSS in Depth 2 精译_057】第九章 CSS 的模块化与作用域 + 9.1 CSS 模块的定义（上）
本篇为《CSS in Depth》全新第2版9.1小节内容的上篇，主要介绍了 CSS 模块化的产生背景及相关概念，并结合上一节层叠图层（cascade layer）的知识，通过一个简单的 messag
阅读更多2024-11-17
分布式事务seata基于docker安装和项目集成seata
分布式系统节点通过网络连接，一定会出现分区问题（P）当分区出现时,系统的一致性和可用性就无法同时满足cp-->不同节点的角色不同ap-->不同节点的角色相同。
阅读更多2024-11-17

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

STL综合

一、数据结构

1. 队列

2. 映射

二、队列例题

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

2. 打印队列

3. 小组队列

4. 日志统计 2.0

三、映射真题

1. 眼红的 Medusa

2. 美食评委

相关文章