POJ 3679 Median 【二分】

题目链接

题意

给N（N小于等于1e6）个数，求出由它们每个数的差组成的数列的中位数（若有偶数个，取左边的一个）

分析

1e6的数据量，直接算是O(n2)的数据量，肯定T。考虑用二分来枚举中位数。然后二分中的判断有不同的方法：

1.O(nlog2n)做法：
用两次二分。先把原来的所有数排序，排序之后，选定一个数，其后面的数与其的差就是递增的了。于是用枚举的中位数，从头到尾遍历，对于遍历到的每一个数，找到有多少数从这个数开始是小于它加上枚举出的中位数的（也即差小于这个中位数），求和就可以判断有多少差值是小于这个枚举出的数了。
这里虽然思路清晰，但是极易写错。同时要考虑这个这个枚举出来数可能有多个。同时，用longlong会T，以后记住int的范围在40亿左右，能用int就用int。将代码贴在这里，以备参考：

//判断函数
bool valid(int a)
{
    int sum=0;
    for(int i=0;i<n-1;++i)
        sum+=upper_bound(X+i+1,X+n,X[i]+a)-(X+i+1);
    --sum;
    return sum>=m;
}

//二分
while(a<b-1)
{
    mid=(a+b)/2;
    if(valid(mid)) b=mid;
    else a=mid;
}
cout<<b<<endl;

2.O(nlogn)做法
在判断那里不用二分，而改用滑动窗口，其实这样还好写一点……（先下面AC代码）

AC代码

//POJ 3579 Median
//AC 2016-8-1 11:33:35
//Binary Search, Two Pointers
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <sstream>
#include <stack>
using namespace std;

#define cls(x) memset(x,0,sizeof x)
#define inf(x) memset(x,0x3f,sizeof x)
#define neg(x) memset(x,-1,sizeof x)
#define ninf(x) memset(x,0xc0,sizeof x)
#define st0(x) memset(x,false,sizeof x)
#define st1(x) memset(x,true,sizeof x)
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define bug cout<<"here"<<endl;
//#define debug

int n;
int X[1000100],m;

bool valid(int a)
{
    int sum=0;
    int p=0,q=0;
    for(p=0;p<n-1;++p)
    {
        while(q<n&&abs(X[q]-X[p])<=a)
            ++q;
        if(q==p) break;
        sum+=q-p-1;
    }
    --sum;
    return sum>=m;
}


int main()
{
    #ifdef debug
        freopen("E:\Documents\code\input.txt","r",stdin);
        freopen("E:\Documents\code\output.txt","w",stdout);
    #endif
    while(scanf("%d",&n)!=EOF)
    {
        m=n;m*=n-1;m/=2;
        if(m&1) m/=2;
        else m=m/2-1;
        for(int i=0;i<n;++i)
            scanf("%lld",&X[i]);
        sort(X,X+n);
        int a=0,b=1000001000,mid;
        while(a<b-1)
        {
            mid=(a+b)/2;
            if(valid(mid)) b=mid;
            else a=mid;
        }
        cout<<b<<endl;
    }
    return 0;
}