【BZOJ1045】【HAOI2008】糖果传递

这道题给的数据范围好鬼畜啊。。

王队说这是傻逼题%%%(虽然的确是的)

听说这题和NOIP2002均分纸牌差不多

那个显然可以贪心:从左到右每次把当前位变成平均数就可以了

这道题设mid为平均数,sum为前缀和则每一位要从后一位拿的个数\(g[i]=g[i-1]+k-a[i]\)

那么发现这个差值是每个点的属性

并且也可以得到\(g[i]=g[1]+sum(g[j]-g[j-1])(j\in(1,i])\)

因为答案为\(g[i]\)的绝对值之和,就可以视为是每个\(sum(g[j]-g[j-1]\)到\(-(g[1]-g[0])\)的距离之和

显然对于每一个起点\(sum(g[j]-g[j-1]\)的相对大小都是不变的

那么只要\(-(g[1]-g[0])\)是这个数组中的中位数即可

剩下就很简单了

说点什么

  Subscribe  
提醒