P4689 谁考了第K名（基础）

解题思路

题目说每个学生的成绩都不同，要我们找出考第 K 名的学生，输出他的学号和成绩。思路很直接：把所有学生按成绩从高到低排序，排好序后第 K 个位置（下标是 K-1）的学生就是答案。下面分五步实现。

**第一步，用结构体存学生。**学生有两个数据：学号（整数）和成绩（浮点数），正好用结构体打包：struct Student { int id; double score; };。

**第二步，写比较规则。**自定义比较函数 cmp，里面写 return a.score > b.score，意思就是成绩高的排前面。因为题目保证成绩互不相同，所以不需要处理分数并列的情况。

**第三步，读入。**用 scanf 读入：%d 读学号，%lf 读浮点成绩，比 cin 更方便。

第四步，排序。sort(students, students + n, cmp) 按成绩从高到低排好。

**第五步，输出。**输出 students[K-1] 的学号和成绩。注意 K 从 1 开始编号，所以数组下标要减 1。

输出有一个小讲究：题目明确说"请使用 %g 输出成绩"。%g 会自动去掉小数末尾多余的 0：比如 68.4 就输出 68.4，而 61 就输出 61，不会输出成 61.000000。如果用 fixed+setprecision 反而可能多出一串 0，所以这里用 cstdio 的 printf 加 %g 最合适。

举个例子验证：5 名学生的成绩分别是 67.8、90.3、61、68.4、73.9，从高到低排序是 90.3（1002 号）、73.9（1005 号）、68.4（1004 号）、67.8（1001 号）、61（1003 号），第 3 名是 1004 号，成绩 68.4，和样例输出完全一致。

边界情况：n 不大，数组开 105 足够；K 的下标容易错，写的时候要特别小心。

参考代码

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

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

// 成绩高的排前面（题目保证成绩都不相同）
bool cmp(const Student &a, const Student &b) {
    return a.score > b.score;
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    Student students[105];
    for (int i = 0; i < n; i++) {
        scanf("%d%lf", &students[i].id, &students[i].score);
    }
    sort(students, students + n, cmp); // 按成绩从高到低排序
    // 第K名在数组里下标是k-1，题目要求用%g输出成绩
    printf("%d %g\n", students[k - 1].id, students[k - 1].score);
    return 0;
}

复杂度分析

排序时间复杂度 O(n log n)，n 很小，非常快。整个程序只有一次 sort 和一趟读入，总时间复杂度 O(n log n)。空间上用一个结构体数组存学生信息，空间复杂度 O(n)。