POJ3579 Median

这是第一篇在POJ的题解2333

URL:POJ

题面描述:

给出n个数,问它们两两之间差的中位数

思路:

先给这些数排序,二分答案它们的中位数,使用lower_bound计算有几个大于$x_i+mid$的,因为如果它大于$x_i+mid$,它在那个数组中的数与$x_i$的差就大于mid了

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;
long long x[N],z[N];
long long n,k,ans;
bool OK(int mi){
long long cnt=0;
for(int i=0;i<n;i++) cnt+=x+n-lower_bound(x+i+1,x+n,x[i]+mi);
return cnt<=k/2;
}
int main(){
while(~scanf("%lld",&n)){
for(int i=0;i<n;i++) scanf("%lld",&x[i]);
sort(x,x+n);
k=n*(n-1)/2;
int l=0,r=*max_element(x,x+n);
while(r-l>1){
int mid=l+(r-l)/2;
if(OK(mid))r=mid;
else l=mid;
}
printf("%d\n",l);
}
return 0;
}