[NOI 2016]国王饮水记

Description

题库链接

给出 \(n\) 个水杯，每个水杯装有不同高度的水 \(h_i\) ，每次可以指定任意多水杯用连通器连通后断开，问不超过 \(k\) 次操作之后 \(1\) 号水杯的最高水量。需要输出 \(q\) 位小数。（提供高精度小数库，单次计算 \(O(q)\) ）

\(1\leq n\leq 8000,1\leq k\leq 10^9,1\leq h_i\leq 10^5\)

Solution

做这道题的过程中想到的几个显然的结论：

• 高度小于 \(h_1\) 的水杯不会对 \(1\) 产生影响；
  • 这样我们一开始处理的时候就可以将高度小于 \(h_1\) 的去掉
• 一个水杯只会被连通一次
• 连接的顺序按高度从小到大
  • 我们可以按高度从小到大排序来做
• 同一组（一起连通的水杯）一定是排好序的连续的一段区间
  • 可以用反证法来证，如果不是这样选，可以通过交换的方式得到连续是更优的解
• 组与组之间没有空隙
  • 如果有空隙，那么可以将高度小一点的组每一个都向更大的选一个，这样一定会更优秀

这样就可以得到一个 \(O(n^2k)\) 的转移。记 \(f_{i,j}\) 表示选了 \(i\) 个组最右端点为 \(j\) 时 \(1\) 号水杯最大的高度为 \(f_{i,j}\) ，转移为

\[f_{i,j}=\max_{0\leq k< j}\left\{\frac{f_{i-1,k}+sum_j-sum_k}{j-k+1}\right\}\]

其中 \(sum\) 是高度的前缀和。

这个式子是可以斜率优化的，并且满足决策单调性，可以做到转移 \(O(nk)\) 。这里显然 \(k=\min\{n,k\}\) 。

不过高精度库计算会有 \(O(p)\) 的复杂度。只能通过 \(70pts\) 。一个比较好的想法就是我们转移过程中还是用 \(double\) 转移，记录下转移方向。最后再算。

虽然理论复杂度似乎可行，不过这样还是过不了...

发现标算用了一个更加奇巧奇淫的性质（考场上我是绝对搞不出来的）

就是选取区间长度是单调不增的，进而可以得到长度大于 \(1\) 的选取的区间最多只有 \(14\) 个（证明的话可以参见年鉴或者题解 \(\text{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)) << "\n";
}
int main() {work(); return 0; }

[NOI 2016]国王饮水记

原文：https://www.cnblogs.com/NaVi-Awson/p/9269874.html