自动搬运

查看原文

来自洛谷，原作者为

	Zvelig1205 Q:3044754855 欢迎来吊打我

搬运于2025-08-24 22:16:24，当前版本为作者最后更新于2021-09-12 17:17:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

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

思路

题目中已经明确指出， $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{玄学})$。

可能是吧， 我太蒻了……

闲话

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

更没有情侣之间好。