国王饮水记

Blog E

有一个长度为 n 的数组 H（元素互不相同），你可以进行 m 次操作，每次取若干元素，把他们都赋值为他们的平均值。求 H1H_1H1​ 最终最大能达到多少，要求计算过程中保留到小数点后 p 位。

贪心一下，大概就能感受出来最优解的搞法：

• 将 H[2,n]H_{[2,n]}H[2,n]​ 排序，选一个后缀，并划分为 m 个区间。
• 把 H1H_1H1​ 从小到大依次和这些区间内的数联通。

这个感觉是对的，但是严格证明需要以下结论：

• 小于等于 H1H_1H1​ 的数没用（显然）
• 假如每次操作都包含 H1H_1H1​，每个数不会选两次（操作过之后就小于等于 H1H_1H1​ 了）
• 存在一个最优方案，每次操作都包含 H1H_1H1​

（借鉴 @lim 的证法）：

考虑最优方案中，最后一次不包含 H1H_1H1​ 的操作，不妨设操作的集合为 S，会发现：S 中的数，之后最多会再被操作一次（之后的操作都包含 H1H_1H1​，由上一个引理可得）。

可以发现，假如不进行这次操作，并把 S 中之后还被操作过的数，从小到大排序之后，替换到上述方案中的位置里，可以得到不劣的答案。

• 相邻两次操作，所选的（除了 H1H_1H1​ 之外的）数，值域不相交（如有相交，改成不相交更优）
• 相邻两次操作，先进行所选的（除了 H1H_1H1​ 之外的）数，较小的操作。（否则交换更优）
• 将 H[2,n]H_{[2,n]}H[2,n]​ 排序，每次操作都是一个区间（如果选的数不连续，可以把第一个数到最后一个数中间所有数都选了（由上上个引理，这些数不可能被别的操作用过），不劣）
• m≥nm\ge nm≥n 的情况与 m=n−1m=n-1m=n−1 相同

把小于 H1H_1H1​ 的东西扔掉，将 H 从小到大排序，记 sH 为 H 的前缀和。

dp(i,j)dp(i,j)dp(i,j) 表示搞完前 i 次操作，并规定 j 之前的东西都不能再操作了，此时 H1H_1H1​ 的最大值。转移显然：

dp(i,j)=max⁡k<j(dp(i−1,k)+sHj−sHkj−k+1)dp(i,j)=\max_{k<j}(\frac{dp(i-1,k)+sH_j-sH_k}{j-k+1})dp(i,j)=k<jmax​(j−k+1dp(i−1,k)+sHj​−sHk​​)

复杂度 O(n3p)O(n^3p)O(n3p)，可得 65 分可以跑路了。

仔细观察转移方程，感觉和一般的斜率优化不太一样，倒是有点 0/1 分数规划的感觉。因此，我们可以考虑二分一个 x，看看需要满足什么条件：

max⁡k<j(dp(i−1,k)+sHj−sHkj−k+1)≥xmax⁡k<j(kx+dp(i−1,k)−sHk)≥(j+1)x−sHj\begin{aligned} \max_{k<j}(\frac{dp(i-1,k)+sH_j-sH_k}{j-k+1})&\ge x\cr \max_{k<j}(kx+dp(i-1,k) - sH_k) &\ge (j + 1)x - sH_j \end{aligned}k<jmax​(j−k+1dp(i−1,k)+sHj​−sHk​​)k<jmax​(kx+dp(i−1,k)−sHk​)​≥x≥(j+1)x−sHj​​

移项之后发现左侧是若干关于 k 的一次函数取 max，也就是一个下凸的玩意，右侧是关于 j 的一次函数。我们要找到一个最大的符合条件的 x，就是要找到右侧函数和左侧凸包的交点。 并且我们发现，这些一次函数虽然截距是小数，但是斜率是整数。因此我们可以轻松算出两个函数的交点，不需要高精度除高精度。

带 log 做法

于是现在我们可以用一个 queue 维护凸包（斜率是单调增的），然后每次查询，二分出凸包和直线的交点在凸包的哪一段上。复杂度 O(n2plog⁡n)O(n^2 p\log n)O(n2plogn)，并没有太多分。

去掉 log

显然，dp(i,j)>dp(i,j−1)dp(i,j)>dp(i,j-1)dp(i,j)>dp(i,j−1)。也就是说，每一次转移，函数与凸包的交点都往右移动。所以我们只需要用一个 deque 维护凸包，在队尾加直线，在队首查询，如果交点超出队首直线的管辖范围，就 pop_front。

复杂度 O(n2p)O(n^2p)O(n2p)。

听说有一个瞎搞做法可以拿分：在前文的基础上，dp 过程只用 double 计算，记录转移点，然后最后用高精度还原答案，复杂度 O(n(n+p))O(n(n+p))O(n(n+p))，但是应该是可以卡的。

根据讲题 ppt，还有个奇妙性质，就是长度不为 1 的区间只有 O(log⁡nh)O(\log nh)O(lognh) 个。因此，数组的第一维只用开到 log⁡nh\log nhlognh，经过实测，开到 5 就能过，O(nplog⁡nh)O(np\log nh)O(nplognh)。

此时，因为 dp 中除法的次数很少，所以用前文的瞎搞做法也是正确的，复杂度 O(n(log⁡nh+p))O(n(\log nh+p))O(n(lognh+p))。

但是我不会证这个性质，看讲题 ppt，总觉得出题人的证明也不太靠谱。比如这页的不等式放缩：

按我的理解，这个不等式应该放缩出来 l≥l\gel≥ 什么东西的。

如果哪位知道这个咋证明，或者我理解错了，还请指出。

O(nplog⁡nh)O(np\log nh)O(nplognh) 做法，省略高精度库。

#define fi first
#define se second
using namespace std;
using pd = pair<Decimal, int>;
const char nl = '\n';
const int MXN = 8005, LG = 5;
pd q[MXN];
int qr, ql;
int n, k, mnk, lim, p, tmp, h0, h[MXN];
Decimal dp[LG + 1][MXN];

Decimal intersec(pd &x, pd &y) { return (x.fi - y.fi) / (y.se - x.se); }
Decimal cal(pd &f, Decimal &x) { return f.fi + f.se * x; }

ostream &operator<<(ostream &x, const Decimal &y) { return x << y.to_string(p + 1); }

int main() {
    /* freopen("P1721.in", "r", stdin); */
    /* freopen("P1721.out", "w", stdout); */
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> p >> h0;
    for (int i = 2, x; i <= n; i++) {
        cin >> x;
        if (x > h0) h[++tmp] = x;
    }

    k = min(k, n = tmp);
    mnk = min(k, LG);
    lim = n - k + mnk;

    sort(h + 1, h + 1 + n);
    partial_sum(h + 1, h + 1 + n, h + 1);
    fill(dp[0], dp[0] + 1 + n, h0);
    for (int i = 1; i <= mnk; i++) {
#define func(x) {dp[i - 1][x] - h[x], x}
        q[qr = ql = 1] = func(0);
        for (int j = 1; j <= n; j++) {
            pd quef = {-h[j], j + 1};
            while (qr > ql && intersec(q[ql], quef) <= intersec(q[ql + 1], quef)) ++ql;
            dp[i][j] = intersec(q[ql], quef);

            pd modf = func(j);
            while (qr > ql && intersec(q[qr - 1], modf) >= intersec(q[qr], modf)) --qr;
            q[++qr] = modf;
        }
    }
    Decimal res = dp[mnk][lim];
    for (int i = lim + 1; i <= n; i++) res = (res + h[i] - h[i - 1]) / 2;
    cout << res << nl;
    return 0;
}

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

阅读量 8

ethan_enhe Edge 98.0.1108.50 Windows 10.0

5 天前回复

Powered By Valine
v1.4.4