可能有的疑问的解答
  • 板块CF671B Robin Hood
  • 楼主Loop1st
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/2 16:38
  • 上次更新2024/8/2 17:46:08
查看原帖
可能有的疑问的解答
766517
Loop1st楼主2024/8/2 16:38

题解做法是二分求最大值和最小值,而 check 函数也很粗暴,检查 xx 是否能成为最大值时只要看 ∑i=1∧ci>xnci−x\sum\limits_{i=1\land c_i>x}^n c_i-x 是否 ≤k\le k,在这时容易产生疑问:有没有一种可能,用了一些天让富人的钱数都变成了 xx,但穷人的钱数 ≥x\ge x 了呢?比如一开始钱数分别为 3,3,3,6,6,63,3,3,6,6,6,在 check 最大值能否为 44 时发现天数只要 99 天,但是很明显,99 天后这堆数里还有 >4>4 的,但其实这种情况不会存在,因为提前设定了最大值最小是总钱数的平均数向上取整,如果我们让分钱的时候尽可能让穷人的钱数 ≤x\le x,那么最后在最坏情况下序列会变成 x,x,x,x,x,...,yx,x,x,x,x,...,y,其中 y>xy>x,但是这种情况下 xx 一定 << 钱数之和的平均数向上取整,所以不会有这种情况。

2024/8/2 16:38
加载中...