题解 CF505E 【Mr. Kitayuta vs. Bamboos】

· · 题解

宣传一波博客

题意

有n根竹子，竹子i初始高度为h_i，每天晚上会长高a_i。

每天白天，你可以选择k根竹子（同一根竹子在同一个白天可以多次选择），把他们的高度减少p，若竹子当前高度-p后<0，则竹子高度变为0。

最小化m天后最高的竹子的高度。

题解

首先最小化最大的...这种问题，显然可以用二分答案。

二分m天后最高的竹子的高度H，然后问题就变成了判定性问题：是否存在一种方案，使得m天后竹子高度都\le H。

考虑怎么解决这个判定性问题。

如果按照题意一天一天模拟，就需要考虑把竹子高度减p后<0的情况，会比较麻烦。

所以我们尝试倒着模拟这一过程。

即：竹子初始高度都设为H，每根竹子每天会减少a_i的高度，然后你可以选择k根竹子，把它们“拔高”p。问m天后竹子高度是否都\ge h_i。

此时你必须保证竹子减少a_i的高度后不会<0。

这样就好做了。我们用一个堆维护 当前状态下继续减少高度而不“拔高”，第m天结束后竹子高度会<h_i的竹子 一直减少高度 多少天后的高度会<0。

（不理解这句话可以尝试看代码理解）

每次取出最快<0的竹子，对它“拔高”即可。注意中间可能会出现无论怎么“拔高”还是会<0的竹子，此时直接返回错误即可。

最后判断堆是否为空即可，因为堆中维护的是m天后竹子高度会<h_i的竹子，所以堆空即代表所有竹子高度都\ge h_i。

时间复杂度O((n+mk)\log n\log mx)，其中mx表示\max\limits_{1\le i\le n} h_i+a_im（二分的上界）。

代码

Code

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
int read(){
    register int x = 0;
    register char f = 1, ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 0;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    return f ? x : -x;
}
int n, m, k, c[100005];
long long p, a[100005], h[100005], l = 0, r, mid, ans;
struct node{
    int day, id;  // 表示当前状态下（二分的高度+c[id]*p）day+1天后竹子id的高度会<0
    bool operator < (const node &b) const {  // 默认大根堆，所以重载<时写的是>
        return day > b.day;
    }
};
struct Heap{  // 用algorithm中的堆相关的算法封装实现。
    node h[200005];
    int sz;
    void clear(){ sz = 0; }
    bool empty(){ return !sz; }
    void push(node x){ h[++sz] = x, std :: push_heap(h + 1, h + 1 + sz); }
    node pop(){ return std :: pop_heap(h + 1, h + 1 + sz), h[sz--]; }
    node top(){ return h[1]; }
}H;
bool check(long long x){
    H.clear(), memset(c, 0, sizeof c); // c[i]表示竹子i被“拔高”了几次
    for (register int i = 1; i <= n; ++i)
        if (x - a[i] * m < h[i]) H.push((node){x / a[i], i});  // 初始堆的状态
    for (register int i = 1; !H.empty() && i <= m; ++i)  // i表示倒着的第几天
        for (register int j = 1; !H.empty() && j <= k; ++j){ // 拔高k根竹子
            node u = H.pop();
            if (u.day < i) return 0;  // 无论怎么“拔高”都不能满足条件
            ++c[u.id];  // “拔高”
            if (x + c[u.id] * p - a[u.id] * m < h[u.id])  // 还是不满足条件，就插入堆中
                H.push((node){(x + c[u.id] * p) / a[u.id], u.id});
        }
    return H.empty();
}
int main(){
    n = read(), m = read(), k = read(), p = read();
    for (register int i = 1; i <= n; ++i)
        h[i] = read(), a[i] = read(), r = std :: max(r, h[i] + a[i] * m);  // 二分上界
    while (l <= r) check(mid = l + r >> 1) ? ans = mid, r = mid - 1 : l = mid + 1;
    printf("%lld", ans);
}

蒟蒻代码，巨佬勿喷。有错误私信哦~