第一轮
第一版(编译错误)
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 使用哈希表记录数据,报名号为键,笔试成绩为值
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
int k, s;
cin >> k >> s;
map.insert(k, s);
}
// 用lambda函数对哈希表排序
sort(map.begin(), map.end(), [](pair<int, int> a, pair<int, int> b) {
if (a.second > b.second) return true;
else if (a.first < b.first) return true;
});
// 计算面试名额,获取面试分数线
int cnt = 1.5 * m;
pair<int, int> temp = map.find(cnt + 999);
int line = temp.second;
cout << line << ' ' << cnt;
for (int i = 0; i < n; i++) {
if(map[i + 999] >= line){
cout << i + 999 << ' ' << map[i + 999];
}
}
}
// 64 位输出请用 printf("%lld")
- 哈希表不能直接排序,它的无序特点在命名中已经体现出来了——
unordered_map
。 map.insert(k, s)
是错的,一定要用insert()
,则创建新的键值对可以这么写——map.insert(make_pair(k, s))
或者map.insert({k, s})
。- 其实,不用
insert()
是更好的做法——map.emplace(k, s)
或者map[k] = s
- 要正确处理向下取整的逻辑,
int cnt = 1.5 * m;
要改成int cnt = static_int(1.5 * m);
。 - 哈希表不能直接用数字索引访问。
- lambda函数要返回完整的比较逻辑。具体来说,有下面这两种写法。
分类讨论:成绩不同时,按成绩降序;成绩相同时,按报名号升序。make_tuple:先按成绩降序,再按报名号升序
sort(candidates.begin(), candidates.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
if (a.second != b.second) {
return a.second > b.second;
} else {
return a.first < b.first;
}
});
sort(candidates.begin(), candidates.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return make_tuple(-a.second, a.first) < make_tuple(-b.second, b.first);
});
第二版
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Candidate{
int id;
int score;
};
int main() {
int n, m;
cin >> n >> m;
vector<Candidate> candidate(n);
for (int i = 0; i < n; i++) {
cin >> candidate[i].id >> candidate[i].score;
}
sort(candidate.begin(), candidate.end(), [](const Candidate& a, const Candidate& b){
if (a.score != b.score) return a.score > b.score;
else return a.id < b.id;
});
int cnt = static_cast<int>(1.5 * m);
int line = candidate[cnt - 1].score;
int i = 0;
while (candidate[i].score >= line) {
i++;
}
cnt = i;
cout << line << ' ' << cnt << endl;
for(int j = 0; j < cnt; j++){
cout << candidate[j].id << ' ' <<candidate[j].score << endl;
}
}
// 64 位输出请用 printf("%lld")
- 自定义结构体,用
vector<Candidate>
储存所有候选人信息,也可以直接用vector<pair<int, int>>
储存。 - 注意可能存在同分情况,因此
cnt
这个值是要更新的。