[NOIP 2009 普及组] 分数线划定

知识点

比较排序、排名、同分处理

解题思路

按分数降序、报名号升序排序。名义面试人数为3*m/2，取该名次的分数为分数线。向后继续纳入所有同分者，输出实际人数及前缀中的报名号和分数。

正确性说明

排序前缀按规定顺序包含所有高于分数线者和一部分等于分数线者；扩展到最后一个同分者后，恰好覆盖全部不低于分数线的人。双关键字比较确保输出同分时编号升序。

易错点

名次从1开始而数组下标从0开始；m1.5应改用整数3m/2；实际人数可能超过名义人数；不能只输出前3*m/2个人。

复杂度

时间O(n log n)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<pair<int,int>>a(n);for(auto&z:a)cin>>z.first>>z.second;sort(a.begin(),a.end(),[](auto x,auto y){return x.second!=y.second?x.second>y.second:x.first<y.first;});int line=a[3*m/2-1].second,cnt=0;while(cnt<n&&a[cnt].second>=line)++cnt;cout<<line<<' '<<cnt<<'\n';for(int i=0;i<cnt;++i)cout<<a[i].first<<' '<<a[i].second<<'\n';}