题意：给出n(3<=n<=100000)个数，f(i,j)=|a[i]-a[j]| (1<=i<j<=n)。求所有的f(i,j)里面中位数的值。
思路：二分答案，再二分检验，注意分辨下是该用upper_bound还是lower_bound. 答案应该是要找最小的满足小于等于他的数>=M个（包括自己）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1e5+5; int a[maxn], n, M; bool judge(int x) { int cnt = 0; for(int i = 1; i < n; i++) cnt += upper_bound(a+i, a+1+n, a[i]+x)-(a+i)-1; return cnt >= M; } int main(void) { while(cin >> n) { for(int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a+1, a+1+n); M = ((1+(n-1))*(n-1)/2+1)/2; int ans, l = 0, r = a[n]-a[1]; while(l <= r) { int mid = (l+r)/2; if(judge(mid)) ans = mid, r = mid-1; else l = mid+1; } printf("%d\n", ans); } return 0; } Sample Input 4 1 3 2 4 3 1 10 2 Sample Output 1 8
