算法
(模拟,排序,多关键字排序) $O(nlogn)$
先将所有同学按分数高者优先、序号小者优先进行双关键字排序。
然后求出分数线:即排名在 $\lfloor 1.5m \rfloor$ 的同学的分数。
最后找出成绩大于等于分数线的同学人数。
时间复杂度
排序是整个算法的瓶颈,这里使用快排,所以总时间复杂度是 $O(nlogn)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int n, m;
struct Person
{
int id, score;
bool operator< (const Person &W)const
{
if (score != W.score) return score > W.score;
return id < W.id;
}
}person[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &person[i].id, &person[i].score);
sort(person, person + n);
int k = m * 1.5;
while (k < n && person[k - 1].score == person[k].score) k ++ ;
printf("%d %d\n", person[k - 1].score, k);
for (int i = 0; i < k; i ++ ) printf("%d %d\n", person[i].id, person[i].score);
return 0;
}
为什么要从0开始
应该是个人习惯