BZOJ_3969_[WF2013]Low Power_二分答案

Description

有n个机器，每个机器有2个芯片，每个芯片可以放k个电池。

每个芯片能量是k个电池的能量的最小值。

两个芯片的能量之差越小，这个机器就工作的越好。

现在有2nk个电池，已知它们的能量，我们要把它们放在n个机器上的芯片上，

使得所有机器的能量之差的最大值最小。

Input

第一行，两个正整数，n和k。

第二行，2nk个整数，表示每个电池的能量。

Output

一行一个整数，表示所有机器的能量之差的最大值最小是多少。

Sample Input

2 3
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output

HINT

2nk <= 10^6, 1 <= pi <= 10^9。

二分答案好题。

首先求最大值最小，能够想到二分答案$x$，然后看能不能塞进去即可。

把每个电池的能量从小到大排序，可以确定每个机器的两个芯片能量最好是相邻的两个数。

如果刚上来第一个和第二个之差就大于$x$了，显然不可以。

如果小于等于$x$，那么接下来可以放$2k$个电池，直到第$2k+1$的位置，如果相邻的差大于$x$就会导致不合法。

以此类推，记录一下之前有多少对数可以被选，有多少对就能使多少$2k$的位置合法。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <queue>

#include <math.h>

using namespace std;

#define N 1000050

int a[N],n,k;

bool check(int x) {

    int i,cnt=n;

    for(i=1;cnt&&i<2*n*k;i++) {

        if(a[i+1]-a[i]<=x) {

            if(2*n*k-i+1<cnt*k*2) return 0;

            i++;

            cnt--;

        }

    }

    return !cnt;

}

int main() {

    scanf("%d%d",&n,&k);

    int i,l=0,r=1000000001;

    for(i=1;i<=2*n*k;i++) {

        scanf("%d",&a[i]);

    }

    sort(a+1,a+2*n*k+1);

    while(l<r) {

        int mid=(l+r)>>1;

        if(check(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d\n",l);

}

秒客网