<题目链接>
题目大意：
给出 N个数，对于存有每两个数的差值的序列求中位数，如果这个序列长度为偶数个元素，就取中间偏小的作为中位数。
解题分析：
由于本题n达到了1e5,所以将这些数之间的差值全部求出来显然是不可行的，这里用的是二分答案。先通过二分，假设枚举出的答案为mid，即，这些数字差值绝对值的中位数为mid。然后我们在通过二分查找，对每一个数字，查找它后面的所有满足与它的差值小于等于mid的数的个数，即查找所有差值小于等于mid的对数。因为中位数所在的编号很容易求得，为 (n*(n-1)/2+1)/2（因为总共有n*(n-1)个差值，题目说了∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N) ）。然后将得到的差值小于等于mid 的对数与mid 的坐标相比较，从而判断该答案的对错。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int M =1e5+5;
typedef long long ll;
int n;
ll arr[M],res; bool juge(ll x){
ll sum=0;
for(int i=1;i<=n;i++)
sum+=lower_bound(arr+i,arr+1+n,arr[i]+x+1)-(arr+i)-1; //这是用于查找小于等于arr[i]+x的数的个数，即与arr[i]绝对值之差小于等于x的数的对数
return sum>=res; //如果大于等于理论值
} int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
scanf("%lld",&arr[i]);
sort(arr+1,arr+n+1);
res=(n*(n-1)/2+1)/2; //小于等于差值中位数的对数
ll l=0,r=arr[n]-arr[1]; //差值最大为arr[n]-arr[1]
while(l<r){
ll mid=(l+r)>>1;
if(juge(mid))r=mid;
else l=mid+1;
}
printf("%lld\n",l);
}
return 0;
}
2018-09-20