USACO analysis
Jczeng |
17 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 2. Loan Repayment
题目大意：
- 给定总牛奶数N，最大天数K，和每天必须还的牛奶量M。
- John每天按照一下规律还牛奶：
- 假设已经还了G加仑牛奶，计算(N-G)/X向下取整，值为Y；
- 如果Y小于M，令Y等于M；
- 还Y加仑牛奶。
- 求得x的最大值。
题目分析：
- 这题表面上看起来可以通过逆推得到X；
- 然而在John每天做的第二点可以看出，X算出的Y可能会被改动：Y=M；
- 也就是说Y可能会有Y=Y+1/Y+2两种情况，又因为(1<=K<=10^12),所以列举两种情况逆推的复杂度必然超时。
- 所以只能换个方向——枚举。
思路：
- 因为给定的三个数据都很大，其中有(1<=M<=10^12)，所以枚举的范围便是(1<=M<=10^12),因此只能用二分查找；
- 剩下的思路便很简单，每通过二分查找得到一个X后，模拟题目看是否可行；
- 然后就是简单的找最大值问题辽！
- （跟上题比起来这真的好轻松啊）
复杂度分析：
- 第一次二分查找的复杂度是O(logN)
- 因为一系列计算可以得到可行会跳过很多天，所以检查的复杂度是O(N^(1/2))
- 所以解法的总体复杂度是O(N^(1/2)logN)
