bzoj3969 LowPower|题解

题意简述:

有n个机器，每个机器有2个芯片，每个芯片可以放k个电池。
每个芯片能量是k个电池的能量的最小值。
两个芯片的能量之差越小，这个机器就工作的越好。
现在有2nk个电池，已知它们的能量，我们要把它们放在n个机器上的芯片上，
使得所有机器的能量之差的最大值最小

自然,求解最大值最小问题应当用二分实现.主程序很容易就能写出来了

int n,k,m;
int arr[1000005];
int main (){
    cin >> n>>k;
    m = ((n * k) << 1);
    for (int i = 1;i <= m;++ i){
        scanf("%d",&arr[i]);
    }
    sort(arr + 1,arr + 1 + m);
    int l = 0,r = arr[m] - arr[1];
    while (l < r){
        int mid = l + ((r - l) >> 1);
        if (!canit(mid))
            l = mid + 1;
        else r = mid;
    }
    cout << l;
    return 0;
}

重点就在于check函数的实现

能否让每一组芯片差值都小于限定值t呢?

此前我们要先给电池分配制定一个最优策略,这个策略的分配方式一定能使满足约束的机器尽量多

而进一步观察还可以发现:对于一颗芯片的k颗电池,只有最小的那颗电池可以决定一个方案的优度,我们称之为有效电池,而剩下的k-1颗电池只不过是用于”凑数”的而已,我们称之为填充电池.不同的两颗芯片交换填充电池(假如它们比有用电池大的话),对结果是没有影响的

那么问题可以解释为:

一个满足约束t的有用电池分配方案,是否有足够的填充电池使这个方案实现??

那么就来分配有用电池

一个有用电池应当是一组k个电池中最小的,因此理应从小到大分配有用电池

而一组芯片的能量差最小,这组芯片的两颗有用电池应当是相邻的(当然事先应该为电池按能量排序)

int j = 1;//为第j组芯片寻找有用电池
int cnt = 0;//记录当前所需的额外填充电池
for (int i = 1;i <= 2*n*k;++ i){
    if (energy[i + 1] - energy[i] <= t)//假如这组电池满足约束,可以作为有用电池
        ++ j,cnt += 2 * (k - 1);//为这组芯片分配k-1个填充电池,并为下一组芯片寻找有用电池
    else
        cnt --;//假如这组电池不满足约束,那第i颗电池永远也没有机会成为有用电池了.但它还可以发光发热--为之前的有用电池充当填充电池(注意这些有用电池一定比第i颗电池能量小,因为它们已经按能量排序了).那么有了这位"志愿者",我们就可以省下一颗额外填充电池
    if (j >= n) return 1;
}

注意:如果分配如上述那样顺利的话,这个方案就是成立的–一颗电池要么作为有用电池,要么作为填充电池,总之没有”永久废弃”的,而题目保证了有恰好2nk颗电池,如果每颗电池都被用到,那这些电池当然就会正好用完.所以这个方案就是成立的

那么反过来,方案不成立是什么情况?出现了”永久废弃”的电池

什么情况下第i颗电池连”别人的填充电池”都无法做到?如果此前的有用电池没有耗费任何一颗额外填充电池,那么第i颗电池也就没办法去替代节省一颗额外填充电池,那么它就被永久废弃了.

于是完整的check函数如下(和上面那份代码实现方式不太一样,不过函数命名的意义是相同的)

bool canit(const int &t){
    int cnt = 0,i = 1;
    for (int j = 1;j <= n;++ j){
        while (cnt >= 0 && arr[i + 1] - arr[i] > t) ++i,--cnt;
        if (cnt < 0) return 0; //一旦没有额外填充电池,就说明出现了永久废弃电池,这种方案就不成立了
        cnt += ((k - 1) << 1);
        i += 2;
    }
    return 1;
}