POJ – 3579 Median(尺取+二分)

给N数字, X1, X2, … , XN，我们计算每对数字之间的差值：∣Xi - Xj∣ (1 ≤ i ＜ j ≤N). 我们能得到 C(N,2) 个差值，现在我们想得到这些差值之间的中位数。如果一共有m个差值且m是偶数，那么我们规定中位数是第(m/2)小的差值。

Input输入包含多测
每个测试点中，第一行有一个NThen N 表示数字的数量。

接下来一行由N个数字：X1, X2, … , XN
( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )Output对于每个样例，输出中位数即可。

Sample Input4
1 3 2 4
3
1 10 2

Sample Output1
8

理解：这道题首先我们可以想到的方法就是暴力枚举 但是毫无疑问 N方的复杂度一定会超时 所以我们用二分+尺取把复杂度降到NlogN

实现方法：
首先我们可以去二分搜索所有的差值可能性 也就是(1e9-0)种可能性 数字虽然打 但使用二分后其实并不慢 然后我们用每次搜索到的差值在原数组中去寻找比这个中位数小的所有数 在这里我们可以使用尺取 把本来需要N方的复杂度降到N 然后记录下这个数的总和 与我们中位数的总数除以二走比较 如果搜索到总数的小于二分中搜索到的那个数 我们就把mid变成start 反之则把mid变成end 直到搜素到一个中位数 比这个数小的综合恰好等于C(N,2)

AC代码：

#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
int a[100010];
int n;
long long flag;
int judge(int median)
{
    int t=0,i;
    long long sum=0;
    for(i=0;i<n;i++)
    {
        while( t<n && a[t]-a[i]<=median)//尺取 
            t++;
        sum+=(t-i-1);
    }
    if(sum>=flag)
        return 1;
    return 0; 
}
int search()//二分枚举 
{
    int start=0;
    int end=1e9;
    int mid;
    while(end-start>1)
    {
        mid=(start+end)/2;
        if(judge(mid))
        end=mid;
        else
        start=mid;
    } 
    return end;
}
int main()
{
    while(~scanf("%d",&n))
    {
        int ans,i,j,tmp;
        flag = (long long)n*(n-1)/2;
        if(flag%2 == 0)
            flag /=2;
        else
            flag = flag/2 + 1;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        ans=search();
        printf("%d\n",ans);
    }
    return 0;
}

这道题在我看来很不好做了 刚开始W了三次 难点一是在于想到如何用尺取+二分 二是在于对于二分的不熟练 还是要对二分的几种边界条件多加注意