P6002 [USACO20JAN] Berry Picking S

· · 题解

题目传送门

数据范围不大，可以直接暴力模拟。

思路

题目中已经明确指出， K 为偶数，所以 \frac{K}{2} 绝对是整数 （当初因为这个专门问了同学） 。

由于题目中没有说每个篮子的上限，那么我们可以枚举篮子装的果子的上限，通过一些奇奇怪怪的比较，来确定最优解。

核心 Code:

for(int i=1;;i++)
{
    priority_queue<int>h;
    basket=0;
    for(int j=1;j<=n;j++)
    {
        basket+=a[j]/i;
        h.push(a[j]%i);
    }
    if(basket>k)continue;
    if(basket<(k>>1))break;
    mei=(k>>1)*i;
    jie=(basket-(k>>1))*i;
    for(int ii=basket-(k>>1)+1;ii<=(k>>1);ii++)
        jie+=h.top(),h.pop();
    ans=max(ans,jie);
}

分步看一下：

basket 代表了需要的篮子数。

很显然，需要的篮子数不能比实际的多，也就有了：

if(basket>k)continue;

当然，也不能太少，就有了：

if(basket<(k>>1))break;

当 basket 在 \frac{K}{2}\sim K 时，也就是部分篮子能装满，部分篮子装不满的情况。

那么，妹妹能拿到其中的 \frac{1}{2}：

mei=(k>>1)*i;

剩下装满的给姐姐，姐姐再从未满的篮子里 贪心的 选取最多的，使自己的利益最大化（优先队列的作用）：

jie=(basket-(k>>1))*i;
for(int ii=basket-(k>>1)+1;ii<=(k>>1);ii++)
    jie+=h.top(),h.pop();

最后，统计姐姐所能得到的最多的浆果数：

ans=max(ans,jie);

优化

首先说明，上述暴力是能 A 掉这个题的。而且这个优化只是我自己想（kouhu）的，并没有尝试，也不知道对不对。

在这里，我们是尝试 枚举答案 ，时间复杂度是 O(n\cdot\text{玄学})。

那么优化就是 二分答案 ，时间复杂度就应该为 O(n\cdot\log\text{玄学})。

可能是吧， 我太蒻了……

闲话

姐妹间的情感就是没有兄弟的好。

更没有情侣之间好。