P17793 [入门赛 #53] 小洛搬西瓜

· · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

题目已经规定了每一步该怎样选择，不需要寻找更优的搬运方案。人数和西瓜数都不超过 300，直接按轮次模拟即可。用 used_j 记录西瓜是否已经搬走，用 ans_i 累加每个小朋友搬走的总重量。

轮到一个小朋友时，从编号最小的西瓜开始查找。遇到已经搬走的西瓜，或者重量超过这个小朋友力量的西瓜，就继续往后找；找到第一个可以搬走的西瓜后，标记它已经搬走，累加重量，并结束这次查找。由于查找始终按编号从小到大进行，选中的就是题目要求的西瓜。每次搬走后立即结束查找，也保证了每次最多搬一个。力量与重量相等时同样可以搬运，所以判断条件是 b_j\leq a_i。

还需要判断什么时候停止。某个小朋友没有搬到西瓜，并不代表其他人也搬不动，因此要等一整轮结束再判断。每轮开始时令 moved 为 false，只要有人搬走西瓜，就改为 true。如果一整轮都没有人搬走西瓜，剩余西瓜在这一轮内始终没有变化，而每个小朋友都检查过它们，说明确实没有人能继续搬运。此时退出循环；如果所有西瓜都已搬完，也会在下一轮通过这个条件退出。

初始时没有西瓜被搬走，所有人的总重量都是 0。之后每次行动都选中题目指定的西瓜，并立即更新标记与总重量，所以程序记录始终与实际过程一致。停止条件也恰好保证剩余西瓜无人能搬，最终的 ans_i 就是答案。参考代码使用从 0 开始的下标，数组中的第 i 个位置对应题面中的第 i+1 个编号。