L2-027 名人堂与代金券
对于在中国大学MOOC（http://www.icourse163.org/ ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 \(60\) 分及以上，并且有另加福利：总评分在 \([G, 100]\) 区间内者，可以得到 \(50\) 元 PAT 代金券；在 \([60, G)\) 区间内者，可以得到 \(20\) 元 \(PAT\) 代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 \(K\) 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 \(PAT\) 代金券。
输入格式：
输入在第一行给出 3 个整数，分别是 \(N\)（不超过 \(10 000\) 的正整数，为学生总数）、\(G\)（在 \((60,100)\) 区间内的整数，为题面中描述的代金券等级分界线）、\(K\)（不超过 \(100\) 且不超过 \(N\) 的正整数，为进入名人堂的最低名次）。接下来 \(N\) 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 \([0, 100]\) 内的整数），其间以空格分隔。题目保证没有重复的账号。
输出格式：
首先在一行中输出发出的 \(PAT\) 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。
输入样例：
10 80 5
[email protected] 78
[email protected] 87
[email protected] 65
[email protected] 96
[email protected] 39
[email protected] 87
[email protected] 80
[email protected] 88
[email protected] 80
[email protected] 70
输出样例：
360
1 [email protected] 96
2 [email protected] 88
3 [email protected] 87
3 [email protected] 87
5 [email protected] 80
5 [email protected] 80
解题思路
模拟题。稍微有点难度的地方在于题中给出了名人堂的最底名次，并且存在并列，这就需要记录上一次所用到的排名编号以及此排名编号的人数。
/* 一切都是命运石之门的选择 El Psy Kongroo */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 10010;
int n, g, k;
vector<psi> p; //存储人的姓名 分数
int sum; //总代金券
int id[N]; //记录排名
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> g >> k;
while(n -- ){
psi cur; cin >> cur.x >> cur.y;
if(cur.y >= 60 && cur.y < g) sum += 20;
else if(cur.y >= g && cur.y <= 100) sum += 50;
p.push_back(cur);
}
cout << sum << endl;
sort(p.begin(), p.end(), [](psi &a, psi &b){
if(a.y != b.y) return a.y > b.y;
return a.x < b.x;
});
int pre = p[0].y, pre_id = 1, cnt = 0; //记录上一次用到的分数及排名 记录处于此排名的人数
id[0] = 1;
for(int i = 1; ; i ++ ){
if(p[i].y == pre) id[i] = pre_id, cnt ++ ; //并列
else if(p[i].y < pre) id[i] = pre_id += cnt + 1, cnt = 0;
pre = p[i].y;
if(pre_id > k) break;
}
for(int i = 0; id[i] <= k && id[i]; i ++ )
cout << id[i] << ' ' << p[i].x << ' ' << p[i].y << endl;
return 0;
}