A6306. 「NOI2016」国王饮水记
编程题
省选/NOI-
知识点
题目描述
跳蚤国有 $n$ 个城市，伟大的跳蚤国王居住在跳蚤国首都中，即 $1$ 号城市中。
跳蚤国最大的问题就是饮水问题，由于首都中居住的跳蚤实在太多，跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用，这导致跳蚤国王也经常喝不上水。
于是，跳蚤国在每个城市都修建了一个圆柱形水箱，这些水箱完全相同且足够高。一个雨天后，第 $i$ 个城市收集到了高度为 $h_i$ 的水。由于地理和天气因素的影响，任何两个不同城市收集到的水高度互不相同。
跳蚤国王也请来蚂蚁工匠帮忙，建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时，可以指定任意多的城市，将这些城市的水箱用地下连通系统连接起来足够长的时间之后，再将地下连通系统关闭。由连通器原理，这些城市的水箱中的水在这次操作后会到达同一高度，并且这一高度等于指定的各水箱高度的平均值。
由于地下连通系统的复杂性，跳蚤国王至多只能使用 $k$ 次地下连通系统。
跳蚤国王请你告诉他，首都 $1$ 号城市水箱中的水位最高能有多高？
跳蚤国最大的问题就是饮水问题，由于首都中居住的跳蚤实在太多，跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用，这导致跳蚤国王也经常喝不上水。
于是，跳蚤国在每个城市都修建了一个圆柱形水箱，这些水箱完全相同且足够高。一个雨天后，第 $i$ 个城市收集到了高度为 $h_i$ 的水。由于地理和天气因素的影响，任何两个不同城市收集到的水高度互不相同。
跳蚤国王也请来蚂蚁工匠帮忙，建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时，可以指定任意多的城市，将这些城市的水箱用地下连通系统连接起来足够长的时间之后，再将地下连通系统关闭。由连通器原理，这些城市的水箱中的水在这次操作后会到达同一高度，并且这一高度等于指定的各水箱高度的平均值。
由于地下连通系统的复杂性，跳蚤国王至多只能使用 $k$ 次地下连通系统。
跳蚤国王请你告诉他，首都 $1$ 号城市水箱中的水位最高能有多高？
输入格式
输入的第一行包含三个正整数 $n,k,p$ 分别表示跳蚤国中城市的数量，跳蚤国王能使用地下连通系统的最多次数，以及你输出的答案要求的精度。$p$ 的含义将在输出格式中解释。
接下来一行包含 $n$ 个正整数，描述城市的水箱在雨后的水位。其中第 $i$ 个正整数 $h_i$ 表示第 $i$ 个城市的水箱的水位。保证 $h_i$ 互不相同，$1 \leq h_i \leq 10^5$。
接下来一行包含 $n$ 个正整数，描述城市的水箱在雨后的水位。其中第 $i$ 个正整数 $h_i$ 表示第 $i$ 个城市的水箱的水位。保证 $h_i$ 互不相同，$1 \leq h_i \leq 10^5$。
输出格式
仅一行一个实数，表示 $1$ 号城市的水箱中的最高水位。
这个实数只可以包含非负整数部分、小数点和小数部分。其中非负整数部分为必需部分，不加正负号。若有小数部分，则非负整数部分与小数部分之间以一个小数点隔开。若无小数部分，则不加小数点。
你输出的实数在小数点后不能超过 $2p$ 位，建议保留至少 $p$ 位。数据保证参考答案与真实答案的绝对误差小于 $10^{-2p}$。
你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 $10^{-p}$。
如果你的输出与参考答案的绝对误差不小于 $10^{-p}$ 但小于 $10^{-5}$，你可以获得该测试点 $40\%$ 的分数。
这个实数只可以包含非负整数部分、小数点和小数部分。其中非负整数部分为必需部分，不加正负号。若有小数部分，则非负整数部分与小数部分之间以一个小数点隔开。若无小数部分，则不加小数点。
你输出的实数在小数点后不能超过 $2p$ 位，建议保留至少 $p$ 位。数据保证参考答案与真实答案的绝对误差小于 $10^{-2p}$。
你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 $10^{-p}$。
如果你的输出与参考答案的绝对误差不小于 $10^{-p}$ 但小于 $10^{-5}$，你可以获得该测试点 $40\%$ 的分数。
输入输出样例
输入 #1
3 1 3 1 4 3
输出 #1
2.666667
输入 #2
3 2 3 1 4 3
输出 #2
3.000000
说明/提示
#### 提示
为保证答案精度，我们一般需要尽可能地在运算过程中保留超过 $p$ 位小数。我们可以证明，在各个子任务的参考算法中都能保证，在任何时候始终保留 $\frac{6}{5}p$ 位小数时，对任何输入得到的输出，与参考答案的绝对误差都小于 $10^{-p}$。
为了方便选手处理高精度小数，我们提供了定点高精度小数类。选手可以根据自己的需要参考与使用该类，也可以不使用该类。其具体的使用方法请参考下发的文档
#### 数据范围
<!-- BEGIN: Migrated markdown table -->
| 测试点编号 | $n$ | $k$ | $p$ |
|-|-|-|-|
| 1 | $\le 2$ | $\le 5$ | $=5$ |
| $2$ | $\le 4$ | $\le 5$ | $=5$ |
| $3$ | $\le 4$ | $\le 5$ | $=5$ |
| 4 | $\le 10$ | $=1$ | $=5$ |
| $5$ | $\le 10$ | $=10^9$ | $=5$ |
| $6$ | $\le 10$ | $\le 10$ | $=5$ |
| $7$ | $\le 10$ | $\le 10$ | $=5$ |
| $8$ | $\le 100$ | $=1$ | $=5$ |
| $9$ | $\le 100$ | $=10^9$ | $=40$ |
| $10$ | $\le 100$ | $\le 10^9$ | $=40$ |
| $11$ | $\le 100$ | $\le 10^9$ | $=40$ |
| $12$ | $\le 100$ | $\le 10^9$ | $=40$ |
| $13$ | $\le 250$ | $\le 10^9$ | $=100$ |
| $14$ | $\le 500$ | $\le 10^9$ | $=200$ |
| $15$ | $\le 700$ | $\le 10^9$ | $=300$ |
| $16$ | $\le 700$ | $\le 10^9$ | $=300$ |
| $17$ | $\le 700$ | $\le 10^9$ | $=300$ |
| $18$ | $\le 2500$ | $\le 10^9$ | $=1000$ |
| $19$ | $\le 4000$ | $\le 10^9$ | $=1500$ |
| $20$ | $\le 8000$ | $\le 10^9$ | $=3000$ |
对于所有数据，满足 $3 \le p \le 3000,1 \le n \le 8000,1 \le k \le {10} ^ 9$。
为保证答案精度，我们一般需要尽可能地在运算过程中保留超过 $p$ 位小数。我们可以证明，在各个子任务的参考算法中都能保证，在任何时候始终保留 $\frac{6}{5}p$ 位小数时，对任何输入得到的输出，与参考答案的绝对误差都小于 $10^{-p}$。
为了方便选手处理高精度小数，我们提供了定点高精度小数类。选手可以根据自己的需要参考与使用该类，也可以不使用该类。其具体的使用方法请参考下发的文档
decimal.pdf。#### 数据范围
<!-- BEGIN: Migrated markdown table -->
| 测试点编号 | $n$ | $k$ | $p$ |
|-|-|-|-|
| 1 | $\le 2$ | $\le 5$ | $=5$ |
| $2$ | $\le 4$ | $\le 5$ | $=5$ |
| $3$ | $\le 4$ | $\le 5$ | $=5$ |
| 4 | $\le 10$ | $=1$ | $=5$ |
| $5$ | $\le 10$ | $=10^9$ | $=5$ |
| $6$ | $\le 10$ | $\le 10$ | $=5$ |
| $7$ | $\le 10$ | $\le 10$ | $=5$ |
| $8$ | $\le 100$ | $=1$ | $=5$ |
| $9$ | $\le 100$ | $=10^9$ | $=40$ |
| $10$ | $\le 100$ | $\le 10^9$ | $=40$ |
| $11$ | $\le 100$ | $\le 10^9$ | $=40$ |
| $12$ | $\le 100$ | $\le 10^9$ | $=40$ |
| $13$ | $\le 250$ | $\le 10^9$ | $=100$ |
| $14$ | $\le 500$ | $\le 10^9$ | $=200$ |
| $15$ | $\le 700$ | $\le 10^9$ | $=300$ |
| $16$ | $\le 700$ | $\le 10^9$ | $=300$ |
| $17$ | $\le 700$ | $\le 10^9$ | $=300$ |
| $18$ | $\le 2500$ | $\le 10^9$ | $=1000$ |
| $19$ | $\le 4000$ | $\le 10^9$ | $=1500$ |
| $20$ | $\le 8000$ | $\le 10^9$ | $=3000$ |
对于所有数据，满足 $3 \le p \le 3000,1 \le n \le 8000,1 \le k \le {10} ^ 9$。