原题链接

考察:二分

思路:

        嵌套二分,和上一题Matrix差不多,中位数和排序后的a数组都具有单调性.

        更好的check函数是,score是a[j]与a[i]的差值,已经确定a[j],那么可以求出a[i]的位置(lower_bound),从而计算前面有多少个符合条件的.

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const int N = 100010;
 8 int n,a[N];
 9 int check(int j,LL score)
10 {
11     int l=0,r = j-1;
12     while(l<r)
13     {
14         int mid = l+r+1>>1;
15         if(a[j]-a[mid]>=score) l = mid;
16         else r = mid-1;
17     }
18     return max(j-l-1,0);
19 }
20 int main() 
21 {
22     while(scanf("%d",&n)!=EOF)
23     {
24         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
25         sort(a+1,a+n+1);
26         LL tmp = (LL)n*(n-1)/2;
27         int t = tmp&1;
28         LL l = 0,r = a[n]-a[1];
29         while(l<r)
30         {
31             LL mid = l+r+1>>1,res = 0;
32             for(int i=2;i<=n;i++)
33               res=res+check(i,mid);
34             if(res<(tmp+t)/2) l = mid;
35             else r = mid-1;
36         }
37         printf("%lld\n",r);
38     }
39     return 0;
40 }