P1068 分数线划定——题解

思路

用结构体保存报名号和成绩，按题目规则排序：

• 成绩不同，成绩高的在前；
• 成绩相同，报名号小的在前。

计算 k = m * 3 / 2，排序后第 k 名的成绩就是分数线。继续向后统计所有成绩不低于分数线的人，即得到实际人数。

复杂度

排序时间复杂度 $O(n\log n)$，额外空间复杂度 $O(n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Student {
    int id, score;
} a[5005];

bool cmp(Student x, Student y) {
    if (x.score != y.score) return x.score > y.score;
    return x.id < y.id;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].id >> a[i].score;

    sort(a + 1, a + n + 1, cmp);
    int k = m * 3 / 2;
    int line = a[k].score;
    int cnt = 0;
    while (cnt < n && a[cnt + 1].score >= line) cnt++;

    cout << line << ' ' << cnt << '\n';
    for (int i = 1; i <= cnt; i++)
        cout << a[i].id << ' ' << a[i].score << '\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; struct Student{int id,score;}a[5005]; bool cmp(Student x,Student y){ if(x.score!=y.score) return x.score>y.score; return x.id<y.id; } int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i].id>>a[i].score; sort(a+1,a+n+1,cmp); int k=m*3/2; int line=a[k].score,cnt=0; while(cnt<n&&a[cnt+1].score>=line) cnt++; cout<<line<<' '<<cnt<<'\n'; for(int i=1;i<=cnt;i++) cout<<a[i].id<<' '<<a[i].score<<'\n'; return 0; }