题解：P14702 [ICPC 2024 Tehran R] Boat

P14702 [ICPC 2024 Tehran R] Boat 题解

题目传送门

贪心，细节较多。

思路分析

先特判无解情况。

提示

• 如果某个重量大于最大载重量 $w$，输出 −1，结束。
• 如果最轻的两个人重量之和超过了 $w$，即无人可以当船夫，输出 −1，结束。

否则一定有解，尽量让两人配对上船，为了用最少次数，先 sort 从小到大排序，再让最轻的人作为船夫，分为两种情况：

• 如果 $a_i+a_1 \leq w$，可以和最轻的人一起上船，可载两人。这样运送要 $2$ 次，$ans \leftarrow ans+2$。
• 否则，不可以和最轻的人一起上船，只载一人。这样运送要 $4$ 次，$ans \leftarrow ans+4$。

最后船夫不回来，所以输出 $ans-1$。

代码

按思路写即可，注意细节，这里不放了。

结语

感谢您的阅读！