P2115 [USACO14MAR]Sabotage G

找一个区间 [ L , R ] [L,R] [L,R],使得删去这个区间之后,剩下数字的平均值最小化. 最小化平均值这个概念有点像01分数规划,那个分式,但这里要求的是连续的区间。 没有办法,尝试列下式子: a n s = ( s u m − s u m ( l , r ) ) / ( n − ( r − l + 1 ) ) ans=(sum-sum(l,r))/(n-(r-l+1)) ans=(sum−sum(l,r))/(n−(r−l+1)) a n s ∗ ( n − r + l − 1 ) = s u m − ( s u m r − s u m l − 1 ) = s u f r + 1 + s u m l − 1 ans *(n-r+l-1)=sum-(sum_r-sum_{l-1})=suf_{r+1}+sum_{l-1} ans∗(n−r+l−1)=sum−(sumr​−suml−1​)=sufr+1​+suml−1​ 感觉和01分数规划非常相似,都是最大化一个分式,模仿01分数规划,分母乘过去,然后化简 a n s ∗ ( n − ( r − l + 1 ) ) ans*(n-(r-l+1)) ans∗(n−(r−l+1))这个式子,意味着有除去区间 [ L , R ] [L,R] [L,R]外个元素的 a n s ans ans,这样 n − ( r − l + 1 ) ) n-(r-l+1)) n−(r−l+1))个 a n s ans ans在数值上等于 ∑ i = r + 1 n a i + ∑ i = 1 l − 1 \sum_{i=r+1}^nai+\sum_{i=1}^{l-1} ∑i=r+1n​ai+∑i=1l−1​ 这就相当于每个区间外每个元素 a i ai ai扣掉 a n s ans ans的值. ∑ ( a i − a n s ) = = 0 \sum(a_i-ans)==0 ∑(ai​−ans)==0 我们二分 a n s ans ans即可,对于二分出来的 a n s ans ans,令 a i − = a n s . a_i-=ans. ai​−=ans. 只要出现一个区间 [ L , R ] [L,R] [L,R]满足 p r e L − 1 + s u f R + 1 < = 0 pre_{L-1}+suf_{R+1}