题解：P10620 [ICPC 2013 WF] Low Power

· · 题解

使满足条件的值最小，这个对答案的定义很二分。

我们考虑对于每一个机器而言真正影响他的芯片功率差的只有最小的两块电池。一块电池如果是芯片中最小的那个，那么同一机器的另一块芯片的最小的电池一定是这块电池的前一个或后一个，换句话说，每次我们选取一个机器两个机器的最小电池时，一定选取两个相邻的电池。

反证法证明：如果这么做不一定是最优的，那么一定有与第 i 块电池相隔几个位置的电池与它匹配在同一机器里，这么做一定不会让答案变小，充其量与我们的决策答案一致，故得证。

我们将数组排好序，如果相邻的两个电池差小于我们二分的答案，说明这两个电池可以作为同一机器两块芯片的最小电池，我们将合法的组数加一。

特别注意！ 并不是只要组数足够就合法的，我们观察下面一组样例。 见代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,m;
int a[1000005];
bool check(int mid){
    int t=0;
    for(int i=1;i<m;i++){
        if(a[i+1]-a[i]<=mid) t++,i++;
        if(i>=t*2*k+1){
            return 0;//它比组数乘电池数乘二的值还要大，前面一定有没有处理的，所以直接舍去即可。
        }
    }
    if(t>=n) return true;
    else return false;
}
signed main(){
    cin>>n>>k;
    m=2*n*k; 
    for(int i=1;i<=m;i++) cin>>a[i];
    sort(a+1,a+1+m);
    int l=0,r=1e18+1;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<l;
    return 0;
}
/*
2 2
1 2 10 12 15 17 20 21
这组数据答案是2，但是为什么不是1呢？
我们考虑它为什么不合法，因为在以20 21开头
的芯片中他们两个不是最小电池，无法左右机器
功率，如何判断一个两个电池是否是还没有被安
排的电池，这个东西很难判断（我卡了好久），
我们换个思路，只要比它小的电池全部被处理结
束了就可以。如何处理，见上面代码。
*/