题解：P1068 [NOIP2009 普及组] 分数线划定

superLouis · 2025-01-19 09:29:41 · 题解

题解：P1068 [NOIP2009 普及组] 分数线划定

就是纯模拟加排序啦。

1. 解题思路

首先，每个人又两个信息，报名号和分数，由此我们想到用结构体。后面还要找前几名，所以排序也是必不可少的，我比较喜欢用重载小于号排序。

找到人数 p 后（m \times 1.5 下取整），先记录下分数线，随后在下标 p+1 到 n 的人中找到与分数线相同的分数就记录下来，并且 p+1。最后输出 1 到 p 的人即可。

2. 代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 5010;
int n, m;
struct node {
    int id, points;
    bool operator < (const node &r) const {
        if (points == r.points) return id < r.id;
        return points > r.points;
    }
} a[maxn]; 
inline int read() {
    register int x = 0, f = 1;
    register char c = getchar();
    if (c == '-') f = -1;
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x * f;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    n = read(); m = read();
    for (int i = 1; i <= n; i++) 
        a[i].id = read(), a[i].points = read();
    sort(a + 1, a + n + 1);
    int p = 1.5 * m, line = a[p].points, cnt = p;
    for (int i = p + 1; i <= n; i++) if (a[i].points == line) cnt++;
    cout << line << " " << cnt << "\n";
    for (int i = 1; i <= cnt; i++) cout << a[i].id << " " << a[i].points << "\n";
    return 0;
}