ZOJ-2091-Mean of Subsequence （反证法的运用！！）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://blog.csdn.net/u014355480/article/details/40862041

ZOJ2091

题意：其实就是找后几个数的平均值的最大值！！ （贪心策略！要找对）





k=1,2,3……n ,记k以及k后面的数的平均值最大的那个k做maxk





一旦Roy选了这个maxk , PMH必定会将所选数字长度最大化





为什么呢？？





用反证法证明：如果所选长度的最后一个数字不是最后一个数n，  而是maxk与n中间的某个数t





那么也就是说ave(maxk...t)<ave(maxk...n)





那么必有 ave(t+1...n)>ave(maxk...n)   说明t+1后面几个数的平均数最大 与题设矛盾