poj3579 Median

思路：

两次二分。首先二分答案，然后通过二分计算比当前候选值大的差值的数量。

实现：

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 const int MAXN = 100005;
 6 ll a[MAXN], n;
 7 ll check(ll x) //大于等于x的差值的个数
 8 {
 9     ll sum = 0;
10     for (int i = 0; i < n; i++)
11     {
12         ll cnt = lower_bound(a, a + n, a[i] + x) - a;
13         sum += n - cnt;
14         if (x == 2) { printf("fucker here: %lld
", cnt); }
15     }
16     return sum >= n * (n - 1) / 4 + 1;
17 }
18 int main()
19 {
20     while (scanf("%lld", &n) != EOF)
21     {
22         for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
23         sort(a, a + n);
24         ll l = 0, r = a[n - 1] - a[0], ans = -1;
25         while (l <= r)
26         {
27             ll m = (l + r) >> 1;
28             if (check(m)) { ans = m; l = m + 1; }
29             else r = m - 1;
30         }
31         printf("%lld
", ans);
32     }
33     return 0;
34 }