题库 信息学奥赛题库 题目列表 完善程序:(中位数 median) 给定 n(n 为奇数且小于...
组合题

完善程序:

(中位数 median) 给定 n(n 为奇数且小于 1000)个整数,整数的范围在 

0∼m(0<m<2 31) 之间,请使用二分法求这 n 个整数的中位数。所谓中位数,是指将这 n 个数排序之后,排在正中间的数。(第五空 2 分,其余 3 分)


#include <iostream>

using namespace std;


const int MAXN = 1000;

int n, i, lbound, rbound, mid, m, count;

int x[MAXN];


int main()

{

    cin >> n >> m;

    for (i = 0; i < n; i++)

        cin >> x[i];

    lbound = 0;

    rbound = m;

    while (①)

    {

        mid = (lbound + rbound) / 2;

        ②;

        for (i = 0; i < n; i++)

            if (③)

                ④;

        if (count > n / 2)

            lbound = mid + 1;

        else

            ⑤;

        cout << mid << " " << lbound << " " << rbound << " " << count << endl;

    }

    cout << rbound << endl;

    return (0);

}

第 1 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
题目信息
完善程序 2015年 初赛
-
正确率
0
评论
49
点击