NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 23 题

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main()
{
    int n,i,sum,x,a[SIZE];
    
    cin>>n;
    memset(a,0,sizeof(a));
    
    for(i=1;i<=n;i++){
        cin>>x;
        a[x]++;
    }
    i=0;
    sum=0;
    while(sum<(n/2+1)){
        i++;
        sum+=a[i];
    }
    cout<<i<<endl;
    return 0;
}

输入： 11 4 5 6 6 4 3 3 2 3 2 1 输出：___________

这题考的是用数组计数排序的思想找中位数。拿到题别急着跑代码，先看数据范围：输入是 1 到 n 的数，所以用下标当数值存频次；后面那个 while 循环就是不断累加频次，直到总数超过 n/2+1，那个下标 i 就是答案，相当于在有序数组里找第 n/2+1 个位置。

最容易错的地方是以为循环里 i 是从 1 开始的，其实代码里 i 初始为 0，第一次就加了 a[0]（频次为 0），这不影响结果但会让学生误判。另一个坑是算 n/2+1 时手误，n=11 时 n/2+1=6，不是 5 或 7。还有学生可能把 a[x]++ 理解成求和，其实只是统计每个数出现了几次。最后输出的是 i 而不是 a[i]，别把下标和值搞混了。

考点与命题视角

这道题属于"程序阅读"类填空题，核心考查两个知识点：一是数组计数（下标即数值），二是通过累加频次找中位数。命题人喜欢在看似复杂的循环里藏简单的逻辑，让学生误以为要模拟排序或二分，其实只要读懂"a[x]++"和"sum+=a[i]"就能秒杀。

概念人话版

1. 计数数组：题目里 a[SIZE] 的大小是 100，但输入只给到 n=11，且每个数都在 1~11 之间。a[x]++ 的意思是：读到一个数 x，就把 a[x] 这个格子加 1。相当于用数组的下标直接存数字，用格子里的值存这个数字出现了多少次。 2. 中位数的下标定义：对于 n 个数，从小到大排好序后，第 n/2+1 个数就是"下中位数"（n=11 时是第 6 个）。程序里 sum 从 0 开始，每次加 a[i]，其实就是把频次从小到大累加，当 sum 第一次超过 n/2+1 时，当前的 i 就是那个数字。

逐行推演（结合输入数据）

输入：

11
4 5 6 6 4 3 3 2 3 2 1

1. cin>>n; → n=11 2. memset(a,0,sizeof(a)); → 全清零，准备计数 3. 循环 for(i=1;i<=n;i++) cin>>x; a[x]++; 统计频次： - 1 出现 1 次 → a[1]=1 - 2 出现 2 次 → a[2]=2 - 3 出现 3 次 → a[3]=3 - 4 出现 2 次 → a[4]=2 - 5 出现 1 次 → a[5]=1 - 6 出现 2 次 → a[6]=2 - 其他 a[7..11] 都是 0 4. 重置 i=0; sum=0; 5. while(sum<(n/2+1)) → n/2+1 = 6，所以条件是 sum<6 - 第 1 轮：i=0, sum+=a[0]=0 → sum=0 < 6，继续 - 第 2 轮：i=1, sum+=a[1]=1 → sum=1 < 6，继续 - 第 3 轮：i=2, sum+=a[2]=2 → sum=3 < 6，继续 - 第 4 轮：i=3, sum+=a[3]=3 → sum=6，此时 sum 不再小于 6，循环结束 6. 输出 i → 3

为什么答案是 3？

把频次按数值从小到大排：

• 1 个数：1 个
• 2 个数：2 个
• 3 个数：3 个
• 4 个数：2 个
• 5 个数：1 个
• 6 个数：2 个

累计：1+2+3 = 6，刚好达到第 6 个位置，对应的数值就是 3。所以程序输出 3 完全正确。

易错点再强调

• 下标从 0 开始：很多人以为 i 应该从 1 开始，但代码里 i=0 是故意的，因为 a[0] 永远是 0，不影响累加，只是让循环多走一步，避免学生误以为漏掉了某个数。
• n/2+1 的计算：n=11 时，整数除法 11/2=5，再加 1 是 6，不是 5 或 7。如果算错成 5，循环会在 sum=5 时就停，输出 i=2，就错了。
• 输出的是 i 不是 a[i]：题目问的是"第 n/2+1 小的数"，而程序输出的是这个数的下标 i，也就是数值本身。别把 i 当成频次去理解。

考频与趋势

• 基础算法：题库共考过 30 题，覆盖 3 个考试级别（2007-2025）。逐年分布：2007 年 2 题、2008 年 1 题、2009 年 4 题、2010 年 4 题、2011 年 5 题、2012 年 1 题、2013 年 1 题、2014 年 2 题、2016 年 1 题、2019 年 1 题、2021 年 4 题、2024 年 2 题、2025 年 2 题。分赛事：NOIP 提高组 初赛 13 题、CSP 提高级 9 题、NOIP 普及组 初赛 8 题。
• 二分查找：题库共考过 39 题，覆盖 7 个考试级别（2008-2026）。逐年分布：2008 年 2 题、2009 年 1 题、2011 年 2 题、2019 年 1 题、2021 年 1 题、2022 年 2 题、2023 年 4 题、2024 年 9 题、2025 年 7 题、2026 年 5 题、null 年 5 题。分赛事：GESP 五级 16 题、GESP 七级 7 题、CSP 入门级 5 题、CSP 提高级 5 题、NOIP 提高组 初赛 3 题、NOIP 普及组 初赛 2 题、GESP 六级 1 题。

预测

从数据看，"基础算法"类题目在 2024-2025 年保持稳定（每年 2 题），"二分查找"类题目在 2024-2026 年爆发式增长（2024 年 9 题、2025 年 7 题、2026 年 5 题），尤其是 GESP 五级在二分查找上占比极高（16 题）。这说明命题人越来越喜欢用"计数 + 累加"这种轻量级技巧来考察二分思想，而不是直接考经典二分。因此，未来 1-2 年，这类"用数组计数找第 k 小"的程序阅读题大概率还会出现在 NOIP 提高组初赛和 CSP 提高级中，但难度不会超过本题——核心还是读懂下标即数值、累加频次到目标位置。

暂无足够依据预测具体的年份和题号，但可以确定的是：只要看到"统计频次 + 累加直到某个阈值"，就要立刻想到"找第 k 小"，答案往往是那个阈值对应的下标。