题解 P1407 【工资】

Dr_殇 · 2017-10-30 21:31:17 · 题解

话说数学中有一个叫做中位数的东西，这道题说人数是大于等于50%，那么不就是求这些人排完序后的中位数吗？

题目分析：

题目很简单，求中位数，但是，让我们来模拟一下。

对于样例的第一组

0 2 0 2 2

排完序后，得

0 0 2 2 2（这是升序，降序也可以）

然后答案就是中间的2

对于样例的第二组

3 4 4 4

答案是4

可得答案就是排完序后的ai/2+1个数

代码如下：

//--新阶梯工作室防伪水印-- 
//--By新阶梯工作室 闪现--
#include <ctime>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[1000005];//定义数组
int main(){
    ios::sync_with_stdio(false);
    scanf ("%d",&n);
    while (n--){
        scanf ("%d",&m);
        int x=m;
        while (x>0){
            scanf ("%d",&a[x--]);//读入
        }
        sort (a+1,a+1+m);//模拟
        printf ("%d\n",a[m/2+1]);//然后输出中位数
    }
    return 0;
}