火影忍者之~静音 | ||||||
|
||||||
Description | ||||||
传说中的火之国一年一度的公务员选拔又开始了!木叶忍者村此次也要从中选拔出5人来,作为即将上任的新火影纲手的小弟~,可是报考公务员的人数实在是太~~多啦!所以纲手的贴身随从—静音小姐,决定对这写人进行分m批的选拔,每次笔试n人,第一次选出5人,之后每次从这n人与之前参加笔试但未选中的人一起再选出分数最高的5人,如果分数相同则按名字的字典序选择,这样下来可以刷掉一大批人,但纲手只需要5人,这时候就轮到静音小姐的跟班小弟—卡卡西,来将这些人再进行二次筛选,卡卡西决定对这些人进行忍术测试,然后选出前5名,作为最后选出的人选,如果忍术分数相同,那么名字字典序靠前的被选中。 |
||||||
Input | ||||||
首先是整数m和n,表示要进行m波笔试,每波n人,然后是m组,每组n行,每行包括一个字符串与两个整数,表示一个人的名字和他的笔试分数以及他的忍术分数。输入到文件结束,m<=100,n<=100名字不长于20,分数不超过100. | ||||||
Output | ||||||
按顺序输出最后选出的5人的名字,每个名字占一行。(第一次选择的时候不需要考虑忍术成绩,第二次选择也不需要考虑笔试成绩) | ||||||
Sample Input | ||||||
1 6 abc 10 20 bcd 20 30 cde 30 40 def 40 50 efg 50 60 fgh 60 70 |
||||||
Sample Output | ||||||
fgh efg def cde bcd |
||||||
Source | ||||||
2012 Spring Contest 3 – STL | ||||||
Author | ||||||
拂晓 |
解题思路:单调队列优化
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>
using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
int n,m;
struct node
{
char ch[30];
int x,y;
friend bool operator <(node a,node b)
{
if(a.x!=b.x) return a.x<b.x;
else return strcmp(a.ch,b.ch)>0;
}
}a[105],pre;
struct node1
{
char ch[30];
int x,y;
friend bool operator <(node1 a,node1 b)
{
if(a.y!=b.y) return a.y<b.y;
else return strcmp(a.ch,b.ch)>0;
}
}pre1;
int main()
{
while(~scanf("%d %d",&m,&n))
{
priority_queue<node>q;
priority_queue<node1>qq;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%s %d %d",a[j].ch,&a[j].x,&a[j].y);
q.push(a[j]);
}
for(int j=1;j<=5;j++)
{
pre=q.top();
q.pop();
strcpy(pre1.ch,pre.ch);
pre1.x=pre.x;
pre1.y=pre.y;
qq.push(pre1);
}
}
for(int i=1;i<=5;i++)
{
pre1=qq.top();
qq.pop();
printf("%s\n",pre1.ch);
}
}
return 0;
}
今天的文章HRBUST1313-火影忍者之~静音分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/63550.html