#224. NOIP2015PJ-28
NOIP2015PJ-28
28.(完善程序)
(中位数median)给定 n(n 为奇数且小于 1000)个整数,整数的范围在 0 至 m(0 < m < )之间,请使用二分法求这 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;
}
①:{{ input(1) }}
②:{{ input(2) }}
③:{{ input(3) }}
④:{{ input(4) }}
⑤:{{ input(5) }}
相关
在下列比赛中: