[NOI Online #3 入门组] 最急救助
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目描述:
救助中心每天都要收到很多求救信号。收到求救信号后救助中心会分析求救信号找出最紧急的求救者给予救助。
求救信号是一个由小写英文字母组成的字符串字符串中连续三个字符依次组成sos的情况越多即包含子串sos的数目越多代表着求救者情况越紧急。
现在请你帮助救助中心找出最紧急的求救者。注意字符串中包含的sos可以有重叠例如sosos算作包含 2 个sos。
输入格式:
从标准输入读入数据。
第一行一个整数 n表示求救者的数目。
接下来有 2×n 行每行一个由小写英文字母组成的字符串。这 2×n 行中第 2×i−11≤i≤n行的字符串表示第 i 个求救者的名字第 2×i 行的字符串表示第 i 个求救者的求救信号。
输出格式:
输出到标准输出。
输出共两行第一行是最紧急求救者的名字。如果最紧急求救者有多个则按照输入的顺序将他们的名字依次输出相邻两个名字间用空格分隔。
第二行一个整数表示最紧急求救者的求救信号中包含有多少个sos子串。
输入输出样例:
输入 #1:
2 adam ineedhelpsosineedhelpsos mark ineedmorehelpsoshelpmesossoshelpme
输出 #1:
mark 3
输入 #2:
3 susan sosososososos jack sossossossos allen soshelpsossossossossos
输出 #2:
susan allen 6
说明/提示:
数据规模与约定:
- 对于 10% 的数据n=1。
- 对于所有数据,1≤n≤100求救者名字长度不超过 20求救信号长度不超过 200。
思路
题目大意就是给你一堆字符串然后让你找出哪个字符串中包含的子串 sos 最多。
所以我们要做的事情有
- 在一个字符串中寻找子串
sos的数量； - 以子串
sos的数量为第一优先级输入顺序为第二优先级排序； - 输出所有子串
sos最多的字符串。
接下来让我们一步一步K掉这道题吧
1.前置存储每个人的信息
这里定义一个结构体即可里面的变量就是每一个求救者的基本信息。这个是最后用来排序的
struct node{
string name,help;
int s,num;
//name 是求助者的名字
//help 是求助者的求助信息
//s 是求助信息中子串 sos 的数量
//num 是求助者的顺序
}str[105];2.第一步
接下来我们需要在一个字符串中寻找子串 sos 的数量这部分是最简单的直接从头到尾暴力枚举即可直接加在结构体里面的s即可,可以写一个函数来进行解决。
int find(string qwq){ //寻找子串 sos 的数量
int len=qwq.size(); //提取出这个字符串的长度STL 大法好QwQ
int anss=0; //子串 sos 的数量
for(int i=0;i<len-2;i++){ //从头到尾枚举
if(qwq[i]=='s'&&qwq[i+1]=='o'&&qwq[i+2]=='s'){ //如果这里有一个 sos
anss++; //子串 sos 的数量+1
}
}
return anss; //返回子串 sos 的数量
}3.第二步
我们就是要开始排序了以子串 sos 的数量为第一优先级输入顺序为第二优先级排序这是题目要求的如果数量相等按照输入顺序输出；
这里也可以利用 STL 中的 sort 函数手写一个 cmp 比较函数即可。
首先是比较函数 cmp
bool cmp(node p,node q){ //比较函数 cmp
if(p.s==q.s){ //如果两个求助信息中的子串 sos 的数量都相同
return p.num<q.num; //按照输入顺序排序
}
return p.s>q.s; //否则按照求助信息中的子串 sos 的数量排序
}然后排序部分只有一行
sort(str+1,str+n+1,cmp); //STL 大法好QWQ第三步
接下来最后一步就是输出了
为了确保输出每一个子串 sos 最多的字符串我们可以定义变量 tmp 来表示子串 sos 最多有多少个然后一个一个输出。
一旦出现子串 sos 少于 tmp 的情况立刻退出循环停止输出因为我们找的是最紧急求救者。
最后输出 tmp 。因为题目中还说让输出最紧急求救者的求救信号中包含有多少个 sos 子串
int tmp=str[1].s; //排序之后最前面的那个自然就是子串 sos 最多的啦QwQ直接记录即可。
for(int i=1;i<=n;i++){
if(str[i].s!=tmp){ //如果子串 sos 的数量少于 tmp
break; //立刻退出循环停止输出
}
cout<<str[i].name<<" ";
}
cout<<endl<<tmp; //别忘了换行哦完整代码
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
string name,help;
int s,num;
//name 是求助者的名字
//help 是求助者的求助信息
//s 是求助信息中子串 sos 的数量
//num 是求助者的顺序
}str[105];
int find(string qwq){ //寻找子串 sos 的数量
int len=qwq.size(); //提取出这个字符串的长度STL 大法好QwQ
int anss=0; //子串 sos 的数量
for(int i=0;i<len-2;i++){ //从头到尾枚举
if(qwq[i]=='s'&&qwq[i+1]=='o'&&qwq[i+2]=='s'){ //如果这里有一个 sos
anss++; //子串 sos 的数量+1
}
}
return anss; //返回子串 sos 的数量
}
bool cmp(node p,node q){ //比较函数 cmp
if(p.s==q.s){ //如果两个求助信息中的子串 sos 的数量都相同
return p.num<q.num; //按照输入顺序排序
}
return p.s>q.s; //否则按照求助信息中的子串 sos 的数量排序
}
int main(){
//freopen("save.in","r",stdin);
//freopen("save.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0); //黑科技cin,cout加速
cin>>n;
for(int i=1;i<=n;i++){
cin>>str[i].name>>str[i].help;
str[i].s=find(str[i].help);
str[i].num=i;
}
sort(str+1,str+n+1,cmp); //STL 大法好QWQ
int tmp=str[1].s; //排序之后最前面的那个自然就是子串 sos 最多的啦QwQ直接记录即可。
for(int i=1;i<=n;i++){
if(str[i].s!=tmp){ //如果子串 sos 的数量少于 tmp
break; //立刻退出循环停止输出
}
cout<<str[i].name<<" ";
}
cout<<endl<<tmp; //别忘了换行哦
return 0;
}总结
这道题作为NOI Online的模拟赛的第三题也就是最后一题属实是太水了我们只需要掌握结构体的运用计数sort排序比较函数排序优先级就可以了连一些算法都不必要用出来。
题目链接
[NOI Online #3 入门组] 最急救助 - 洛谷https://www.luogu.com.cn/problem/P6565