【BZOJ4654】【NOI2016】国王饮水记

首先目测一下。。如果没有次数使用限制怎么搞最好?

首先比\(1\)号城市水箱低的没什么用,不但没贡献还会把别的水箱拉低。

那么要让\(1\)号城市最终尽可能高,就要让其他城市的高度之和尽可能低。

首先每次只和一个城市连接最优。如果和\(n\)个城市连接,相当于\(1\)号城市先与较低的\(n-1\)个城市连接,再与这\(n\)个城市连接,那么这样最高的城市的水有一部分流入了那\(n-1\)个城市,显然不如第二次单独连接最高的城市。

那么每次连接的城市水箱高度一定是递增的。假设有两个城市\(x,y\),那么如果先连接\(x\),\(h_1\)变为\(\frac{h_1}{4}+\frac{h_x}{4}+\frac{h_y}{2}\),显然先连接更低的优。

考虑次数限制,每次就可能合并多个。

考虑合并带来的损失,以两个为例:

令\(h_y>h_x>h_1\):

若一个一个合并,\(h_1\)变为\(\frac{h_1}{4}+\frac{h_x}{4}+\frac{h_y}{2}\);

若一起合并,\(h_1\)变为\(\frac{h_1}{3}+\frac{h_x}{3}+\frac{h_y}{3}\);

损失\(\frac{2h_y-h_x-h_1}{12}\)。

所以对于一个固定的\(x\),合并的\(y\)越低越好。于是猜测每次合并的一定是排序后的一段区间。如果不是一段区间,将所选中最大的元素替换成区间内某个未选数显然更优。

那么同样,一次与\(n\)个城市合并相当于先不计次数地合并\(n\)个城市再与\(1\)城市合并。因为取的是一段区间,这样合并不会改变原来的合并顺序。

对于相邻两个区间,设数较小的长度为\(x\),和为\(X\),较大的长度为\(y\),和为\(Y\)。

如果将较大区间的最小数\(A\)移动到较小区间:

\(\frac{\bar{x}+\frac{h_1}{x}}{y}+\bar{y}\)变为\(\frac{\bar{x}’+\frac{h_1}{x+1}}{y-1}+\bar{y}’\)

当\(y\ge x+1\)时\(xy\ge (x+1)(y-1)\),移动后一定更优。

所以每段长度从小到大一定单调不上升。

然后有一个不知道怎么(打表)来的结论:在所有水量高度互不相同的情况下,长度大于\(1\)的区间仅有\(log\)个。

这样由于高精度小数库的复杂度为\(O(p)\),然后听说决策是单调的,那么就可以用斜率优化\(O(nplogn)\)解决了。

(大部分是瞎猜+伪证,意会就好233)

说点什么

2 评论 在 "【BZOJ4654】【NOI2016】国王饮水记"

提醒
排序:   最新 | 最旧 | 得票最多
成员

这道题真的是BZOJ的4652么

wpDiscuz