P4670 谁考了第K名（基础）

解题思路

第一步，把信息打包。 每个同学有两个信息——学号 id 和成绩 score，它们必须成对出现、一起移动，不能分开。用结构体 Stu 把学号和成绩装在一起，就像一张登记卡；再开一个数组 students 存 n 张登记卡。

第二步，读入信息。 用循环依次读入每个同学的学号和成绩，存进 students[i].id 和 students[i].score。

第三步，按成绩排序。 调用 sort 时给它一个自定义规则 cmp：成绩高的排前面。sort(students, students + n, cmp) 排完后，数组第 0 个是第一名、第 1 个是第二名……第 k-1 个就是第 K 名，因为数组下标从 0 开始数。

第四步，输出第 K 名。 用 printf 输出下标 k-1 那个同学的学号和成绩。成绩是小数，如果直接用 cout 输出，可能会多出多余的 0，比如 61 会变成 61.0。用 %g 格式能自动去掉小数末尾多余的 0：61 输出 61，68.4 输出 68.4，最清爽。

想一想生活里的例子。 体育课上老师让全班同学按跑步成绩排队，跑得快的站前面。如果队伍已经按成绩从高到低排好，从队头数第 K 个同学就是第 K 名。

边界情况： n 可能比较大，数组开 1005 足够；第 K 名存在数组下标 k-1 的位置，不要和"第几个"搞混。

参考代码

// P4670 谁考了第K名：按成绩从高到低排序，输出第K名的学号和成绩
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Stu {
    int id;      // 学号
    double score; // 成绩
};

bool cmp(const Stu &x, const Stu &y) {
    return x.score > y.score; // 成绩高的排前面
}

Stu students[1005];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> students[i].id >> students[i].score;
    }
    sort(students, students + n, cmp); // 按成绩从高到低排序
    printf("%d %g\n", students[k - 1].id, students[k - 1].score); // %g去掉小数末尾多余的0
    return 0;
}

复杂度分析

sort 对 n 个元素排序的时间复杂度是 O(n log n)，空间上只需要 O(n) 存下所有学生。本题 n 最大 1000 左右，log n 大约 10，整体非常快，一秒内轻松完成。