【二分答案】【贪心】bzoj3969

http://www.cnblogs.com/mmlz/p/4497118.html

#include<cstdio>
#include<algorithm>
using namespace std;
int n,K,nn,a[1000001],sumv[1000002];
bool check(int x)
{
    int cnt=0,i;
    for(i=1;i<nn;)
      {
        if(a[i+1]-a[i]>x)
          {
            sumv[i]=1;
            ++i;
          }
        else
          {
            sumv[i]=sumv[i+1]=0;
            ++cnt;
            i+=2;
            if(cnt==n)
              break;
          }
      }
    if(cnt<n)
      return 0;
    for(;i<=nn;++i) sumv[i]=1;
    cnt=0;
    for(i=nn;i;--i)
      {
        int t=sumv[i];
        sumv[i]+=sumv[i+1];
        if(!t)
          {
            ++cnt;
            if(sumv[i]<cnt*(K-1))
              return 0;
          }
      }
    return 1;
}
int main()
{
//  freopen("bzoj3969.in","r",stdin);
//  freopen("bzoj3969.out","w",stdout);
    scanf("%d%d",&n,&K);
    nn=((n*K)<<1);
    for(int i=1;i<=nn;++i)
      scanf("%d",&a[i]);
    sort(a+1,a+1+nn);
    int l=0,r=1000000000;
    while(r>l)
      {
        int mid=(l+r>>1);
        if(check(mid))
          r=mid;
        else
          l=mid+1;
      }
    printf("%d
",l);
    return 0;
}