Stressful Training（CF1132D）

题意

有 $n$ 个学生要打一场 $k$ 分钟的比赛。(n,k<=2e5)

每个学生的电脑有初始电量 $a_i$ 和每分钟耗电量 $b_i$ （电量在这一分钟的最后一刻结算，即在下一分钟时才会减少，最终电量允许为负）。(ai<1e12,bi<1e7)

学生们买了一个充电器，功率为任意值，每分钟可以使电量增加 $x$ 。D

问题：求最小的 $x$ ，使所有学生的电脑的电量在 $k$ 分钟内都不为负。

思路

二分答案+贪心。每分钟都给当前续航时间最少的电脑充电，如果续航时间相同给耗电量大的电脑先充电，都相同则给剩余电量少的电脑先充电。那么可以按照此规则维护一个优先队列，每次给队首元素充电，如果其续航时间超过k则弹出队列。一共执行k次，若当前续航时间小于当前天数则失败，撑过k天或者队列为空则成功。优先队列的建堆复杂度 $O(n)$ ，插入删除为 $O(log n)$ ，算法复杂度为 $O((n+k\cdot logn)log_2{10}^{12})$ 。

二分右边界开太大爆long long了一次。还要注意优先队列定义规则里面的大于号和小于号。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
ll al[maxn], be[maxn];
ll n,k;
const ll inf = 2e12;
struct node {
    ll d, a, b; // d=a/b
    node (ll dd, ll aa, ll bb) {
        d=dd; a=aa; b=bb;
    }
    bool operator < (const node &p) const { // 最后还有一个const
        if(d == p.d && b == p.b) return a>p.a;
        if(d == p.d) return b<p.b;
        return d > p.d;
    }
};

priority_queue<node> q;

bool check(ll mid) {
    priority_queue<node> qq=q;
    for(int i=0;i<k;i++) {
        if(qq.empty()) return 1;
        node p=qq.top();
        qq.pop();
//        cout << p.d << ' ' << p.a <<  " " << p.b << endl;
//        cout<<p.d <<"  " << i << endl;
        if(p.d < i) return 0;
        if((p.a+mid)/p.b < k) {
            qq.push(node((p.a+mid)/p.b, p.a+mid, p.b));
        }
    }
    return 1;
}

int main() {
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++) scanf("%lld",&al[i]);
    for(int i=0;i<n;i++) scanf("%lld",&be[i]);
    for(int i=0;i<n;i++) {
        if(al[i]/be[i] < k)
            q.push(node(al[i]/be[i],al[i],be[i]));
    }
    ll l=0,r=inf,ans=inf,mid;
    while(l<=r) {
//        cout << "mid = " << mid << endl;
        mid = (l+r)>>1;
        if(check(mid)) ans = min(ans, mid), r=mid-1;
        else l=mid+1;
    }
    if(ans==inf) ans=-1;
    printf("%lld\n", ans);
}