给出n个数字， 对每个 取出每个 ai- aj . 问中位数是什么
这道题是二分套二分。。 先二分枚举答案， 然后二分验证
假设中位数是x
ai-aj = x (j<i 原数组先排序） 那么对于每个0~n aj + x 就是 最小的 ai , 那么就可以认为 i~n 去减去aj都会比x大。 最后统计个数
题目：
Description
Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi- Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!
Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.
Input
The input consists of several test cases.
In each test case, N
will be given in the first line. Then N numbers are given, representing
X1, X2, ... , XN, (
Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000
)
Output
For each test case, output the median in a separate line.
Sample Input
4 1 3 2 4 3 1 10 2
Sample Output
1 8
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 #define LL long long 7 #define INF 100000000+10 8 LL n; 9 LL num[100000+10]; 10 11 bool C(LL x) 12 { 13 LL cnt =0 ; 14 for(int i=0;i<n;i++) 15 { 16 cnt += (num+n) - lower_bound(num+i+1,num+n,num[i]+x); 17 } 18 LL m =(LL)n*(n-1)/2; 19 if( cnt >=m/2+1)return true; 20 return false; 21 } 22 int main() 23 { 24 while(scanf("%d",&n)!=EOF) 25 { 26 for(int i=0;i<n;i++) 27 { 28 scanf("%lld",&num[i]); 29 } 30 sort( num ,num+n); 31 LL lb = 0 , rb = INF; 32 LL mid , ans; 33 while( lb<=rb) 34 { 35 mid = (lb+rb)/2; 36 if(C(mid)) 37 { 38 lb = mid+1; 39 ans = mid; 40 } 41 else 42 { 43 rb = mid-1; 44 } 45 } 46 printf("%lld\n",ans); 47 } 48 return 0; 49 }