给定n个数a,…,a。求n个数字当中第|到第r个数当中的中位数,我们可以用二分的经典思想来解决此问题。所谓中位数就是“个数中从小到大排序第n/2+1个数。
#include<bits/stdc++,h>
using namespace std
}const int MAXN-le3+10;
int n,m,alMAXN],maxn;
int main(){
cin>>n>>m/
for (int i=l;i<=n;i++)
cin>>a[i],
maxn=max(maxn,a[i]);
while(m--){
int lft,rgt;
cin>>lft>>rgt,int 1=1,r= while( ②)intmid= ③s1=0,s2=0;
for(int i=lft;i<=rgt;i++){
if(a[i]>mid)s1++;
if(a[i]<mid)s2++;
if(s1<=s2)④ =mid;
else ⑤=mid;
}cout<<l;
return 0;
1处应填
maxn
maxn+1
maxn-1
n*2
2处应填
l+r<n
l<=r
l<r
l+1<r
3处应填
I+r
(1+r)>>1
r-]+1
r-1
4处应填
1
r
lft
rgt
5处应填
1
r
lft
rgt
发表评论