思路:
不需要具体存储差值, 可以利用二分判定直接找到本题利用了lower_bound函数(在algorithm类中), 用法: lower_bound(a,a+n,x), 返回的是,在a中第一次大于或者等于x的地址. 如果a是数组, 返回的是指针类型, 如果是vector, 返回的是iterator类型. test函数中, cnt记录的是小于 a[i]+val(临时差值) a [ i ] + v a l ( 临 时 差 值 ) 的元素个数, 如果累和起来大于m( C2n/2 C n 2 / 2 , 即差值集合元素个数的一半), 说明主函数中, mid落在差值集合的二分右半侧.代码:
#include <iostream> #include <cstdio> #include <algorithm> #define fo(i,a,b) for(int i = a;i < b; i++) #define MAX 100005 using namespace std; int a[MAX]; int m; int ans = -1; int n; bool test(int val) { int cnt = 0; fo(i,0,n) cnt += n-( lower_bound(a,a+n,a[i]+val) - a); return cnt > m; } int main() { while(~scanf("%d",&n)) { m = n*(n-1) >> 2; fo(i,0,n) scanf("%d",&a[i]); sort(a,a+n); int l = 0; int r = a[n-1]-a[0]; while(l<=r) { int mid = (l+r) >> 1; if(test(mid)) { ans = mid; l = mid+1; } else r = mid-1; } printf("%d\n",ans); } return 0; }
启示:
利用两分法找中位数时, 不一定需要知道每个元素的具体值, 可以根据一个判定函数(如本题中的test()函数),来判定是在左半侧还是右半侧, 最终得到中位数.