poj 3579 Median (尺取法+二分)
题意：给出n个数，两两做差的绝对值，共有m=n*(n-1)/2个，问其中的中位数是多少。特别地，当m为偶数的时候，中位数为第m/2个。
思路：二分中位数。
一开始还觉得由于中位数在整数意义上不连续不能二分。。。。
但是最后结果不可能是那样的答案啊。。。
check的条件是，以k为中位数的时候，绝对值小于k的数要小于(m+1)/2个（也就是中位数所在的位置）
check的时候尺取即可。
复杂度 排序O(nlgn) + 二分(lgn)*尺取O(n) ，整体O(nlgn)
1/* ***********************************************
2Author :111qqz
3Created Time :Tue 20 Sep 2016 12:18:19 AM CST
4File Name :code/poj/3579.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32LL n,m;
33int x[N];
34bool check( int k)
35{
36 int cnt = 0 ; //cnt为绝对值小于k的对数,小于中位数的对数应该小于m个。
37 int head = 1;
38 int tail = 1;
39 while (head<=n)
40 {
41 while (x[tail]-x[head]<k&&tail<=n) tail++;
42 tail--;
43 cnt+=(tail-head);
44 head++;
45 }
46 return cnt>=m;
47}
48int bin()
49{
50 int l = 0 ;
51 int r = x[n] - x[1];
52 while (l<=r)
53 {
54 int mid = (l+r)>>1;
55 if (check(mid)) r = mid-1;
56 else l = mid+1;
57 }
58 return l-1;
59}
60int main()
61{
62 #ifndef ONLINE_JUDGE
63 freopen("code/in.txt","r",stdin);
64 #endif
65 while (scanf("%lld",&n)!=EOF){
66 for ( int i = 1 ; i <= n ; i++ ) scanf("%d",&x[i]);
67 sort(x+1,x+n+1);
68 m = n*(n-1)/2;
69 m = (m+1)/2;
70 int ans = bin();
71 printf("%d\n",ans);
72 }
73#ifndef ONLINE_JUDGE
74 fclose(stdin);
75 #endif
76 return 0;
77}