BZOJ4654 [Noi2016]国王饮水记-布布扣-bubuko.com

Description

跳蚤国有 n 个城市，伟大的跳蚤国王居住在跳蚤国首都中，即 1 号城市中。跳蚤国最大的问题就是饮水问题，由

于首都中居住的跳蚤实在太多，跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用，这导致跳蚤国王也经常喝

不上水。于是，跳蚤国在每个城市都修建了一个圆柱形水箱，这些水箱完全相同且足够高。一个雨天后，第 i 个

城市收集到了高度为 hi 的水。由于地理和天气因素的影响，任何两个不同城市收集到的水高度互不相同。跳蚤国

王也请来蚂蚁工匠帮忙，建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时，可以指定任意多的

城市，将这些城市的水箱用地下连通系统连接起来足够长的时间之后，再将地下连通系统关闭。由连通器原理，这

些城市的水箱中的水在这次操作后会到达同一高度，并且这一高度等于指定的各水箱高度的平均值。由于地下连通

系统的复杂性，跳蚤国王至多只能使用 k 次地下连通系统。跳蚤国王请你告诉他，首都 1 号城市水箱中的水位最

高能有多高？

Input

输入的第一行包含 3 个正整数 n,k,p分别表示跳蚤国中城市的数量，跳蚤国王能使用地下连通系统的最多次数，

以及你输出的答案要求的精度。p 的含义将在输出格式中解释。接下来一行包含 n 个正整数，描述城市的水箱在

雨后的水位。其中第 i 个正整数 hi 表示第 i 个城市的水箱的水位。保证 hi 互不相同，1≤hi≤10^5

对于所有数据，满足3≤p≤3000,1≤n≤8000,1≤k≤10^9

Output

仅一行一个实数，表示 1 号城市的水箱中的最高水位。这个实数只可以包含非负整数部分、小数点和小数部分。

其中非负整数部分为必需部分，不加正负号。若有小数部分，则非负整数部分与小数部分之间以一个小数点隔开。

若无小数部分，则不加小数点。你输出的实数在小数点后不能超过 2p 位，建议保留至少 p 位。数据保证参考答

案与真实答案的绝对误差小于 10^-2p。你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 10^-

Sample Input

3 1 3
1 4 3

Sample Output

2.666667
explanation
由于至多使用一次地下连通系统，有以下 5 种方案：
1. 不使用地下连通系统：此时 1 号城市的水箱水位为 1。
2. 使用一次连通系统，连通 1、2 号：此时 11 号城市的水箱水位为 5/2。
3. 使用一次连通系统，连通 1、3 号：此时 1 号城市的水箱水位为 2/2。
4. 使用一次连通系统，连通 2、3号：此时 1 号城市的水箱水位为 1。
5. 使用一次连通系统，连通 1、2、3号：此时 11 号城市的水箱水位为 8/3。

正解：

解题报告：

　　Picks出的NOI中神题

　　首先列出所有要用到的定理：

　　1、所有水量小于等于1号城市水量的城市都不对答案产生贡献。

　　（这个应该是显然的吧...）

　　（下面略去“在最优方案中”辣）

　　2、除一号城市外，每个城市最多被连通一次。

　　3、每一次连通都一定和1号城市连通。

　　（待更新......）

BZOJ4654 [Noi2016]国王饮水记

原文：http://www.cnblogs.com/ljh2000-jump/p/6376109.html