Stressful Training_牛客博客

题意

有 $n$ 台电脑,每台电脑，他的初始电量为 $a_i$ ，每分钟消耗电量为 $b_i$ 你有一个功率为 $x$ 的充电器，每分钟可以使一台电脑电量增加 $x$ 。
问， $k$ 至少为多大才能保证在 $[0,k)$ 的时间内任意一台电脑电量都不为负

思路

直接二分充电器的功率。那么接下来就考虑如何 $check()$ 这个功率值 $x$ 。考虑使用优先队列，按照还能使用的时间排序，每次贪心的选取可以撑的时间最少的加上 $x$ 的电，然后每当有可以超过 $k$ 的，就直接移出队列，当队列为空时，便为成功，然后继续二分即可.

代码

#include<bits/stdc++.h>
#define ll long long
const ll N=1e6+5,INF=2e12;
using namespace std;

ll n,k;
ll a[N],b[N],ans=-1;
struct node
{
    ll a,b,c;
    bool operator < (const node &x)const
    {
        if(c!=x.c)
            return c>x.c;
        if(b!=x.b)
            return b<x.b;
        return a>x.a;
    }
};

inline ll read()
{
    register ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

priority_queue<node> Que;

bool check(ll x)
{
    while(!Que.empty()) Que.pop();
    for(int i=1;i<=n;i++)
        if(a[i]/b[i]<k)
            Que.push({a[i],b[i],a[i]/b[i]});
    if(Que.empty())
        return 1;
    for(int i=0;i<k;i++)
    {
        node t=Que.top();
        Que.pop();
        if(t.c<i)
            return 0;
        if((t.a+x)/t.b<k)
            Que.push({t.a+x,t.b,(t.a+x)/t.b});
        if(Que.empty())
            return 1;
    }
    return 1;
}

int main()
{
    n=read();k=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    for(ll i=1;i<=n;i++) b[i]=read();
    ll l=0,r=INF;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}