@[ethan_zhou](/user/124740)
下面把 $A_1$ 说成 $a$,默认 $k \geq 2$。
令另外 $2$ 个城市水位为 $b,c$,且 $b<c$。
首先明确 $b,c$ 必须大于 $a$,不然绝对用不到。
分类讨论:
* $a$ 不连
显然不优。
* $a$ 连 $b$,不连 $c$
显然不优。
* $a$ 连 $c$ 不连 $b$
显然不如先连 $b$ 再连 $c$ 优。
* $a$ 连 $b$ 和 $c$
先连 $c$ 再连 $b$:$\frac{\frac{a+c}{2}+b}{2}=\frac{3a+6b+3c}{12}$
先连 $b$ 再连 $c$:$\frac{\frac{a+b}{2}+c}{2}=\frac{3a+3b+6c}{12}$
先连 $b$ 和 $c$,再连 $a$:$\frac{\frac{b+c}{2}+a}{2}=\frac{6a+3b+3c}{12}$
直接连 $a,b,c$:$\frac{4a+4b+4c}{12}$
前 $3$ 个很明显可以看出,先连 $b$ 再连 $c$ 更优,再跟第 $4$ 种比较,前者 - 后者得到 $\frac{-a-b+2c}{12}$,因为 $a<b<c$,所以 $-a-b+2c>0$,所以还是前者更优。
既然 $a$ 跟任意 $2$ 个比它大的数连都满足这个性质,那拓展到多个也满足。
感性理解就是这样。这题要用到贪心的思维方法但是不是贪心题所以我没写,有错误请指教。
by 0htoAi @ 2022-02-14 01:32:16
@[ethan_zhou](/user/124740) 可以参照
https://lim.blog.luogu.org/p1721-noi2016-guo-wang-yin-shui-ji
by _LiM @ 2022-02-14 08:13:28
@[_LiM](/user/56724) @[0htoAi](/user/335366) thx
by ethan_zhou @ 2022-02-14 16:29:38