Teek is Loading...
主题
设 fi 表示玩到第 i 轮时的期望。
将 A 从小到大排序,可知一段前缀会取到 fi+1,剩下的后缀会取到 Aj,这个分界点可以二分找到,若 k>0,前缀最终会变为空,此时无需再继续递归,因此 O(nlogn) 递推即可。
若 k=0,每一轮的代价都相等,可以进行无限轮,因此每一轮面对的情况都相等,则有
即
当 f→f+1,左边增加 ≤1,右边增加 1,故方程具有单调性,二分 f 即可。