NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 24 题

#include<iostream>
using namespace std;
int main()
{
    const int SIZE=10;
    int data[SIZE],i,j,cnt,n,m;
    cin>>n>>m;
    for(i=1;i<=n;i++)
       cin>>data[i];
    for(i=1;i<=n;i++)
    {
        cnt=0;
        for(j=1;j<=n;j++)
            if( (data[i]<data[j]) || (data[j]==data[i] && j<i) )
                cnt++;
        if (cnt==m)
            cout<<data[i]<<endl;
    }
    return 0;
}

输入： 5 2 96 -8 0 16 87 输出：_______

别急着看循环条件，先把这串数字从大到小排一排，数数每个数排第几，题目里的 cnt 其实就是它在降序里的排名，m 是你要找的第几名的位置，对照着就能秒杀。

很多学生看到 cnt 统计的是‘比它小或相等且下标更小’的个数，容易误以为是升序排名或者搞反了大小关系，导致把 16 看成 0 或者 -8。其实只要记住：cnt 等于‘比它大的数’加上‘和它一样大但位置更靠前的数’，合起来就是降序排列中的下标（0 基），m=2 就是找第三大的数，千万别被负数干扰了直觉。

考点与概念 这题考的是“程序阅读 + 排名统计”。核心概念很简单：对一个序列，按从大到小排好，第 0 个最大，第 1 个第二……题目里的 cnt 就是在模拟这个过程，不用真的排序，直接数数。

命题人挖坑点 命题人喜欢把条件写得绕一点：data[i] < data[j] 或者 data[j] == data[i] && j < i。学生容易只盯着前半句，觉得 cnt 就是“比它小的个数”，然后去数比它大的，结果全反了。还有一个坑是负数，输入里有 -8，很多学生看到负数就慌，其实负数只是普通整数，大小比较逻辑不变。

拿到题先想什么？ 1. 先读输入：n=5，m=2，数组是 96 -8 0 16 87。 2. 理解循环：外层 i 从 1 到 n，内层 j 也从 1 到 n，对每个 data[i] 统计满足条件的 j 的个数 cnt。 3. 翻译条件： - 如果 data[j] 比 data[i] 大，cnt++； - 如果 data[j] 和 data[i] 一样大，但 j 比 i 小（也就是在 data[i] 前面出现过），cnt++。 换句话说，cnt = “比它大的数” + “和它一样大且排在它前面的数”。 4. 联想排名：把整个数组从大到小排，cnt 正好就是 data[i] 在降序里的下标（0 基）。比如最大的数 cnt=0，第二大的 cnt=1…… 5. 看输出条件：当 cnt == m 时输出 data[i]。所以题目就是让输出“第 m+1 大”的数。

一步步推演（不用真写排序） 输入数组：96, -8, 0, 16, 87

• i=1, data[1]=96：没有比它大的，也没有相等的，cnt=0 ≠ 2，不输出。
• i=2, data[2]=-8：比它大的有 96、0、16、87，共 4 个，cnt=4 ≠ 2，不输出。
• i=3, data[3]=0：比它大的有 96、16、87，共 3 个，cnt=3 ≠ 2，不输出。
• i=4, data[4]=16：比它大的有 96、87，共 2 个；有没有相等的？没有。cnt=2 == m，输出 16。
• i=5, data[5]=87：比它大的只有 96，cnt=1 ≠ 2，不输出。

为什么答案是 16？ 因为 m=2，程序找的是降序排名为 2 的元素（第三大）。把数组降序排：96, 87, 16, 0, -8。第三大就是 16，和上面逐元素统计的结果完全一致。

易错再提醒

• 别把 cnt 当成“比它小的个数”，那样你会算出 96 的 cnt=4，-8 的 cnt=0，完全对不上。
• 别忽略“相等且下标更小”这一条，如果数组里有重复值，比如 5,5,5，中间那个 5 的 cnt 会是 2（前面两个 5），而第一个 5 的 cnt 是 0，第三个 5 的 cnt 是 2，这样排名才会唯一。
• 别被负数吓到，大小比较是纯数值比较，-8 比 0 小，比 16 小，逻辑和普通整数一样。

考频与趋势 排序基础（含排名、选择排序、冒泡排序等）是信息学竞赛的高频考点。题库里共考过 249 题，覆盖 9 个级别，从 2008 年到 2026 年每年都有出现。近年趋势明显上升：2023 年 22 题、2024 年 51 题、2025 年 57 题、2026 年 50 题，说明命题人越来越喜欢考“不直接排序，而是通过统计或模拟来间接求排名/第 k 小”这类变式题。

未来怎么考？ 基于数据，未来大概率继续考“统计型排名”：给出一个数组，让你求第 k 小/第 k 大，或者求某个元素的排名，但不会让你真的写排序代码，而是让你读懂一段嵌套循环、用条件计数来模拟排序过程。还可能结合“稳定排序”的概念，考察相等元素的下标顺序是否影响排名。这类题通常 n 在 100~1000 之间，时间复杂度要求 O(n²) 也能过，重点在于理解 cnt 的含义。

暂无足够依据预测具体年份的题型分布，但可以肯定的是：只要理解“cnt = 降序排名”，这类题就能快速秒杀。