CF1132D Stressful Training

题目大意

有台电脑，一共要撑过分钟
对于每台电脑，他的初始电量为，每分钟消耗电量为
问，至少需要一个功率(每分钟)为多大的充电器才能保证的电量都不为负

分析

按照贪心的思想，对于每一分钟，充电器应该用给那个还能坚持的时间最小的那个
这一定是一个必要操作，正确性显然

对于初始电量可以撑过分钟的电脑，可以忽略不管

那么对于两种功率的充电器，可以简单证明，如果可以满足条件，则一定满足条件
这满足二分答案的性质

所以就可以用二分答案来求得需要的答案（二分右界设为无穷大）

对于操作，可以用一个优先队列/小根堆之类的东西来维护
首先表示的是这台电脑能用多久，显然是要小的在堆顶
然后弹出堆顶，给他冲的电量，在丢回堆

对于相等的电脑，是要让大的在前面；
对于都相等的电脑，就是让小的在前面

这样的贪心应该不需要多解释了

于是，在函数中，就可以枚举时间
只要在某一时刻，堆顶的小于了当前时间，即可return false
只要在某一时刻，堆中没有元素了，即可return true
然后，给堆顶的电脑冲点电，整理一下堆，就可以了

时间复杂度

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, k;
ll a[maxn], b[maxn];
ll l(0), r(2e12), ans(-1);

struct Node {
    ll a, b, c;
    Node () {}
    Node (ll a, ll b, ll c) : a(a), b(b), c(c) {}
    bool operator < (const Node &T) const {
        if (c ^ T.c) return c > T.c;
        else if (b ^ T.b) return b < T.b;
        return a > T.a;
    }
};

inline bool Check(ll x)
{
    priority_queue <Node> Q;
    for (int i = 1; i <= n; ++i) 
        if (a[i] / b[i] < k) Q.push(Node(a[i], b[i], a[i] / b[i]));

    if (Q.empty()) return 1;

    for (int i = 0; i < k; ++i) {
        Node temp = Q.top();
        Q.pop();
        if (temp.c < i) return 0;
        if ((temp.a + x) / temp.b < k) Q.push(Node(temp.a + x, temp.b, (temp.a + x) / temp.b));
        if (Q.empty()) return 1;
    }

    return 1;
}

signed main()
{
    n = __read(), k = __read();
    for (int i = 1; i <= n; ++i) a[i] = __read();
    for (int i = 1; i <= n; ++i) b[i] = __read();

    while (l <= r) {
        ll mid ((l + r) >> 1);
        if (Check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    printf ("%lld\n", ans);
    system("pause");
}