hdu7471 最优K子段(口胡题解 二分+贪心+随机化)
题目
思路来源
官方题解
题解
最大化min还是逃不出二分,
随机是为了质数这个限制条件而生的
由于每n个数有n/logn个质数,所以期望意义上每logn个数会有一个质数
二分答案mid,能用最早的段达到mid则用最早的段达到,所以set维护前缀和及其下标
由于是sum[i]-sum[j]>=mid,i-j为质数,所以需要i-j是质数且sum[j]尽可能小
那么,用set维护没用过的前缀子段,set上暴力遍历若干个最小的值即可