#P4654. [Noi2016]国王饮水记

    ID: 2871 传统题 3000ms 256MiB 尝试: 202 已通过: 97 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS贪心交换论证动态规划线性 DP排序与序列处理一维前缀和凸包优化 DP单调队列数值计算与优化有理数精确运算枚举与搜索路径恢复模拟与实现技巧高精度除法CF3000

[Noi2016]国王饮水记

[NOI2016] 国王饮水记

题目描述

跳蚤国有 nn 个城市,伟大的跳蚤国王居住在跳蚤国首都中,即 11 号城市中。

跳蚤国最大的问题就是饮水问题,由于首都中居住的跳蚤实在太多,跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用,这导致跳蚤国王也经常喝不上水。

于是,跳蚤国在每个城市都修建了一个圆柱形水箱,这些水箱完全相同且足够高。一个雨天后,第 ii 个城市收集到了高度为 hih_i 的水。由于地理和天气因素的影响,任何两个不同城市收集到的水高度互不相同。

跳蚤国王也请来蚂蚁工匠帮忙,建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时,可以指定任意多的城市,将这些城市的水箱用地下连通系统连接起来足够长的时间之后,再将地下连通系统关闭。由连通器原理,这些城市的水箱中的水在这次操作后会到达同一高度,并且这一高度等于指定的各水箱高度的平均值。

由于地下连通系统的复杂性,跳蚤国王至多只能使用 kk 次地下连通系统。

跳蚤国王请你告诉他,首都 11 号城市水箱中的水位最高能有多高?

输入格式

输入的第一行包含三个正整数 n,k,pn,k,p 分别表示跳蚤国中城市的数量,跳蚤国王能使用地下连通系统的最多次数,以及你输出的答案要求的精度。pp 的含义将在输出格式中解释。

接下来一行包含 nn 个正整数,描述城市的水箱在雨后的水位。其中第 ii 个正整数 hih_i 表示第 ii 个城市的水箱的水位。保证 hih_i 互不相同,1≤hi≤1051 \leq h_i \leq 10^5。

输出格式

仅一行一个实数,表示 11 号城市的水箱中的最高水位。

这个实数只可以包含非负整数部分、小数点和小数部分。其中非负整数部分为必需部分,不加正负号。若有小数部分,则非负整数部分与小数部分之间以一个小数点隔开。若无小数部分,则不加小数点。

你输出的实数在小数点后不能超过 2p2p 位,建议保留至少 pp 位。数据保证参考答案与真实答案的绝对误差小于 10−2p10^{-2p}。

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

若绝对误差不小于 10−p10^{-p} 但小于 10−510^{-5},该测试点可获 40%40\% 的分数。

样例 1

3 1 3
1 4 3
2.666667

样例 2

3 2 3
1 4 3
3.000000

样例 3

100 36 40
285 22874 53293 58043 24740 29719 2636 79533 28747 96171 46022 96607 26620 17991 12944 30391 85093 90255 29007 46366 24942 96448 58894 6807 1550 36199 21662 59661 51346 9753 54132 13919 85760 96089 63925 95432 30218 70028 77936 6559 74040 93814 10371 97480 61954 73668 23930 549 18350 5304 31413 86900 96323 44518 52936 18669 33892 11388 70132 4171 46347 83014 36386 19316 92235 55942 55467 77965 39756 25130 67345 83434 39326 78106 6959 46912 82571 84447 47101 7150 30758 63867 67378 93849 28647 35691 1280 22707 57416 38981 66645 94766 74280 7053 93648 87069 92906 53687 20138 90949
96955.94174742806515294230646557278103298611111111111111111111111111111111111111111111

提示

样例解释 1

由于至多使用一次地下连通系统,有以下五种方案:

  1. 不使用地下连通系统:此时 11 号城市的水箱水位为 11。
  2. 使用一次连通系统,连通 11、22 号:此时 11 号城市的水箱水位为 5/25/2。
  3. 使用一次连通系统,连通 11、33 号:此时 11 号城市的水箱水位为 22。
  4. 使用一次连通系统,连通 22、33 号:此时 11 号城市的水箱水位为 11。
  5. 使用一次连通系统,连通 11、22、33 号:此时 11 号城市的水箱水位为 8/38/3。

样例解释 2

此时最优方案为使用两次连通系统,第一次连通 1,31,3 号,第二次连通 1,21,2 号。

提示

为保证答案精度,我们一般需要尽可能地在运算过程中保留超过 pp 位小数。我们可以证明,在各个子任务的参考算法中都能保证,在任何时候始终保留 65p\frac{6}{5}p 位小数时,对任何输入得到的输出,与参考答案的绝对误差都小于 10−p10^{-p}。

为了方便选手处理高精度小数,我们提供了定点高精度小数类。选手可以根据自己的需要参考与使用该类,也可以不使用该类。其具体的使用方法请参考下发的文档 decimal.pdf,该文档及示例代码收录于 原赛附件。

数据范围

1≤n≤80001\le n\le8000,1≤k≤1091\le k\le 10^9,3≤p≤30003\le p\le3000。下表列出原赛各测试点的范围和精度参数。

测试点编号 nn kk pp
1 ≤2\le 2 ≤5\le 5 =5=5
22 ≤4\le 4
33
4 ≤10\le 10 =1=1
55 =109=10^9
66 ≤10\le 10
77
88 ≤100\le 100 =1=1
99 =109=10^9 =40=40
1010 ≤109\le 10^9
1111
1212
1313 ≤250\le 250 =100=100
1414 ≤500\le 500 =200=200
1515 ≤700\le 700 =300=300
1616
1717
1818 ≤2500\le 2500 =1000=1000
1919 ≤4000\le 4000 =1500=1500
2020 ≤8000\le 8000 =3000=3000