| by XianKa | 1 comment

【19HDU多校】HDU-6651 Final Exam(田忌赛马问题)

传送门

题意是说有n个问题,总共有m分。你如果想通过某个问题,你就需要复习大于该问题分数的时间。
但是你不知道每个问题是多少分。问题是你至少要复习多少时间才能保证通过至少K个问题。

解法是反向思考。

如果我是老师,那么我假设知道了学生的复习计划。那么我肯定会把他复习最多的 k – 1 个问题都设置为0分。这样我就有 m 分去尝试卡掉剩下的 n – k + 1 个问题。而这 n – k + 1 个问题也肯定是学生复习时间最少的几个问题。因为复习时间最长的 k – 1 个问题我已经设置为难度为0。

这也就是田忌赛马策略。

而对于剩下的 n – k + 1个问题。如果老师想都卡掉,那么最好的办法就是对于每一个问题,都设置为他复习时间那么多分,使得他刚刚无法通过。如果最后我 m 分刚好用完,或者还剩余。那么学生就被老师卡掉了。

反之,如果每道题设置复习时间那么多分数,m 分不够。那么学生就无法被卡掉。

这样看来,对于学生来说。只要最少的 n – k + 1 个复习时间,的总复习时间大于 m 那么就无法被卡掉。剩下的 k – 1 个时间都是大于最少的 n – k + 1 个复习时间的。那么这些时间一共最少是m + 1。(鸽巢原理,m 分放在 m + 1 的题上,总有一个题会过)

那么问题就变成了:有 n – k + 1 个数之和为 m + 1,且要求这些数里面最大的数字最小。

很明显这个最大的数字最小的时候就是平均分配 m + 1 分的时候。

所以,答案公式即ceil((m + 1) / (n – k + 1)) * (k – 1) + m + 1

这道题的贪心思路反向思考,考虑如果方案已经确定,如何构造最坏情况。根据最坏情况做出的决策一定是最优解

1 Comment

yukun

4月 4, 2020, 5:08 下午 回复

只有你这篇看懂了

发表评论