HRBUST1313-火影忍者之～静音

科技前沿 • 2025-02-08 11:24 • 阅读 48

大家好，我是讯享网，很高兴认识大家。

火影忍者之～静音

Time Limit: 1000 MS

Memory Limit: 32767 K

Total Submit: 353(87 users)

Total Accepted: 101(73 users)

Rating:

讯享网

Special Judge: No

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>; 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; .push(pre1); } } for(int i=1;i<=5;i++) { pre1=.top(); .pop(); printf("%s\n",pre1.ch); } } return 0; }

讯享网

HRBUST1313-火影忍者之～静音

相关推荐