传送门

题意是说有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

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