bzoj3969 LowPower|题解

bzoj3969 LowPower|题解

三月 11, 2018

题意简述:

有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;
    }