Description
给出 (n) 个水杯，每个水杯装有不同高度的水 (h_i) ，每次可以指定任意多水杯用连通器连通后断开，问不超过 (k) 次操作之后 (1) 号水杯的最高水量。需要输出 (q) 位小数。（提供高精度小数库，单次计算 (O(q)) ）
(1leq nleq 8000,1leq kleq 10^9,1leq h_ileq 10^5)
Solution
做这道题的过程中想到的几个显然的结论：
- 高度小于 (h_1) 的水杯不会对 (1) 产生影响；
- 这样我们一开始处理的时候就可以将高度小于 (h_1) 的去掉
- 一个水杯只会被连通一次
- 连接的顺序按高度从小到大
- 我们可以按高度从小到大排序来做
- 同一组（一起连通的水杯）一定是排好序的连续的一段区间
- 可以用反证法来证，如果不是这样选，可以通过交换的方式得到连续是更优的解
- 组与组之间没有空隙
- 如果有空隙，那么可以将高度小一点的组每一个都向更大的选一个，这样一定会更优秀
这样就可以得到一个 (O(n^2k)) 的转移。记 (f_{i,j}) 表示选了 (i) 个组最右端点为 (j) 时 (1) 号水杯最大的高度为 (f_{i,j}) ，转移为
[f_{i,j}=max_{0leq k< j}left{frac{f_{i-1,k}+sum_j-sum_k}{j-k+1} ight}]
其中 (sum) 是高度的前缀和。
这个式子是可以斜率优化的，并且满足决策单调性，可以做到转移 (O(nk)) 。这里显然 (k=min{n,k}) 。
不过高精度库计算会有 (O(p)) 的复杂度。只能通过 (70pts) 。一个比较好的想法就是我们转移过程中还是用 (double) 转移，记录下转移方向。最后再算。
虽然理论复杂度似乎可行，不过这样还是过不了...
发现标算用了一个更加奇巧奇淫的性质（考场上我是绝对搞不出来的）
就是选取区间长度是单调不增的，进而可以得到长度大于 (1) 的选取的区间最多只有 (14) 个（证明的话可以参见年鉴或者题解 ( ext{PPT}) ）。
那么复杂度就是 (O(14n+pn)) 的了。
Code
#include <bits/stdc++.h>
using namespace std;
// ---------- decimal lib start ----------
//为了美观，这里略去了高精度小数库。
//只要将题目提供的高精度小数库粘在这里就是完整的代码了。
// ---------- decimal lib end ----------
const int N = 8000+5;
#define pdd pair<double, double>
#define fr first
#define sc second
int n, k, p, h[N], tot, h1, sum[N], head, tail, q[N], pre[15][N], lim;
double f[15][N];
pdd a[N], t;
Decimal ans;
double K(pdd a, pdd b) {return (b.sc-a.sc)/(b.fr-a.fr); }
void cal(int i, int j) {
if (i == 0 || j == 0) ans = h1;
else {cal(i-1, pre[i][j]); ans = (ans+sum[j]-sum[pre[i][j]])/(j-pre[i][j]+1); }
}
void work() {
scanf("%d%d%d", &n, &k, &p);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]); h1 = h[1];
for (int i = 1; i <= n; i++) if (h[i] > h1) h[++tot] = h[i];
n = tot; sort(h+1, h+n+1); k = min(n, k);
for (int i = 1; i <= n; i++) sum[i] = sum[i-1]+h[i];
lim = min(14, k);
for (int i = 0; i <= n; i++) f[0][i] = h1;
for (int i = 0; i <= lim; i++) f[i][0] = h1;
for (int i = 1; i <= lim; i++) {
head = tail = 0; q[tail] = 0; a[0] = pdd(-1, -h1);
for (int j = 1; j <= n; j++) {
t = pdd(j, sum[j]);
while (head < tail && K(a[q[head]], t) < K(a[q[head+1]], t)) ++head;
f[i][j] = (f[i-1][q[head]]+sum[j]-sum[q[head]])/(1.*j-q[head]+1);
pre[i][j] = q[head];
a[j] = pdd(j-1, 1.*sum[j]-f[i-1][j]);
while (head < tail && K(a[q[tail-1]], a[q[tail]]) > K(a[q[tail]], a[j])) --tail;
q[++tail] = j;
}
}
int locj = n-(k-lim), loci; double maxn = 0;
for (int i = 1; i <= lim; i++) if (f[i][locj] > maxn) maxn = f[i][locj], loci = i;
cal(loci, locj);
for (int i = locj+1; i <= n; i++) ans = (ans+h[i])/2;
cout << ans.to_string(int(1.5*p)) << "
";
}
int main() {work(); return 0; }