2993专题

HDU-2993 二分-至少连续k个平均值最大(数形结合)

题目连接 分析讲解 题意:在n个序列中找出至少k个连续的数,使它们平均值最大,输出最大的值。 题意转化:用sum()求出前n个数的和,那么p=(sum(j)-sum(i-1))/(j-i+1) ,j-i>=k+1;把sum(i)看做y轴的值,i看做x轴的值,由于ai>0;所以图形是: 一条递增的凹凸不平的折线。那么问题就是:在这条折线上找出横坐标的值至少相差k,他们的之间的连线斜率最大。