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
1
HINT
\(2nk \le 10^{6}, 1 \le p_{i} \le 10^{9}\)。
答案明显满足可二分性，我们可以利用贪心检验。
我们将所有的\(power\)从小到大排个序。然后二分一个结果\(mid\)，从左往右枚举\(i\)，如果\(power_{i+1}-power_{i} \le mid\)，就选择这两个电池作为能量最小的电池装到一个机器人上，直到选出\(2n\)个。最后我们只需要检验是否每个电池都可以在它后面跟上\(K-1\)个电池即可。这个从左往右for一遍贪心即可。
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define maxn (1000010)
int N,K,power[maxn],cho[maxn];
inline bool check(int key)
{
int nn = 0;
for (int i = 1;i < (N*K<<1)&&nn < (N<<1);++i) if (power[i+1]-power[i] <= key) cho[++nn] = i,cho[++nn] = i+1,++i;
if (nn != (N<<1)) return false;
for (int i = nn,last = (N*K<<1)+1,tot = 0;i;--i)
{
tot -= cho[i]-last; tot -= K; last = cho[i];
if (tot < 0) return false;
}
return true;
}
int main()
{
freopen("3969.in","r",stdin);
freopen("3969.out","w",stdout);
scanf("%d %d",&N,&K);
for (int i = 1;i <= (N*K<<1);++i) scanf("%d",power+i);
sort(power+1,power+(N*K<<1)+1);
int l = 0,r = 1<<30;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
printf("%d",l);
fclose(stdin); fclose(stdout);
return 0;
}