200字范文,内容丰富有趣,生活中的好帮手!
200字范文 > CF_671B Robin Hood(二分)

CF_671B Robin Hood(二分)

时间:2023-01-03 04:50:40

相关推荐

CF_671B Robin Hood(二分)

题意:

有一列数字,从大的往小的拿使最大最小值相差最小,每次只能拿一个,最多拿K次。

思路:

首先依据题意,求最小的极值确定下来是二分。刚开始想的是二分极值或最小值,但是判断函数十分难写。后来参考网上的思路对最大值和最小值分别进行二分,找到最大的最小值和最小的最大值,然后求出最小极值。很好的解题思路!但是注意两次二分的取值范围:对于最小值我们在0~sum/N之间二分,也就是说最小值一定不超过平均值(不可能超过平均值);对于最大值我们在(sum+N-1)/N~INF之间二分,最大值一定大于平均值。

上面的这句话是错误的,第一遍的时候这里没有想清楚,但是现在能够理解了。

更正为:对于最大值我们在(sum+N-1)/N~INF之间二分,最大值大于等于平均值。

考虑一种临界情况是sum刚好为n的整数倍,这个时候最大值和最小值应该都等于平均值,所以最大值的下边界也一定要从平均值开始。

起初一直在想为什么不能用(sum+n)/n,就是在于上面这种情况,如果sum为n的整数倍&#x

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。