poj 3579 Median 二分套二分 或 二分加尺取

Median

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?5118	?	Accepted:?1641

Description

Given?N?numbers,?X₁,?X₂, ... ,?X_N, let us calculate the difference of every pair of numbers: ∣X_i?-?X_j∣ (1 ≤?i?＜?j?≤?N). We can get?C(N,2)differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the?(m/2)-th? smallest number if?m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of?m?= 6.

Input

The input consists of several test cases.
In each test case,?N?will be given in the first line. Then?N?numbers are given, representing?X₁,?X₂, ... ,?X_N, (?X_i?≤ 1,000,000,000? 3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Sample Input

4
1 3 2 4
3
1 10 2

Sample Output

1
8

Source

POJ Founder Monthly Contest – 2008.04.13, Lei Tao

題意：給你N個數字，求這些數字兩兩之差的絕對值的中位數

二分套二分：核心還是要抓住<x的數量>=m（內層二分）的最小x（外層二分）-1才是該序列中的第m小的數，有不理解的話可以看本博客另一篇講的很詳細的文章

下面的第一份代碼是使用了lower_bound，復雜度是n(logn)*(logn)；時間是563ms#include<cstdio>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
int  a[100005];
long long   l,r,m,n;
int ok(int  x)
{int  cnt=0;for(int i=1;i<=n;i++)cnt+=lower_bound(a+i,a+n+1,a[i]+x)-(a+i)-1;
//lower_bound降低時間復雜度return cnt>=m;
}
int main()
{while(~scanf("%lld",&n)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);m=n*(n-1)/2;if(m%2==0) m=m/2;else m=(m+1)/2;l=0,r=a[n]-a[1];while(r-l>1){int mid=(r+l)>>1;///枚舉得到<x的數量>=m的最小x；if(ok(mid))r=mid;elsel=mid;}printf("%lld\n",r-1);}return 0;
}

　　有個小技巧是在ok()函數內統計絕對值<x的數量可以不適用lower_bound而使用尺取法

可以降低復雜度,復雜度是(logn)*n,時間只有300多ms

int ok(int  x)
{int  cnt=0;for(int i=1,j=1;i<=n;i++){while(a[j]-a[i]<x&&j<=n)j++;cnt+=(j-1-i);}return cnt>=m;
}