NOIP 普及 2011 第一轮 第 25 题：用频次数组求中位数

题目

```
#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

阅读程序写结果

答案

3

题解

考点定位

本题考「计数数组模拟」,对应大纲 4.2.1 程序模拟（难度【3】）。

解题过程

11 个数：4,5,6,6,4,3,3,2,3,2,1。计数：a[1]=1,a[2]=2,a[3]=3,a[4]=2,a[5]=1,a[6]=2。

while 找累加和 ≥ n/2+1 = 6 的最小 i：

输出 3。

易错提醒

① 该程序求「第 ⌈n/2⌉ 小的值」（多数元素/中位数变体）；② 累加条件 sum<(n/2+1) 是整数除法 n/2=5 ⇒ 目标 6。