Stressful Training

Stressful Training

分析

• 这是个贪心
• 注意到每次只能给一个人的电脑充电，那么考虑最优的充电的顺序。而这个最优的顺序便是先给最早没电的电脑充电(但是我不会证明诶QwQ)。于是只需要用一个优先队列存储一下每一个人的电脑电量消耗完的时间，二分枚举x判
  断能否符合题目条件

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>

#define ll long long

using namespace std;

const int N=2e5+10;

ll n,k;
ll a[N],b[N];

struct nkl
{
    ll id,rem,now;
    bool operator < (const nkl &b)const
    {
        return rem>b.rem;
    }
};


inline bool check(ll mid)
{
    priority_queue<nkl>q;
    for (ll i=1;i<=n;i++)
    {//计算每一台电脑会在第几分钟没电 
        ll th=a[i]/b[i]+1;
        q.push((nkl){i,th,a[i]});
    }

    for (ll i=1;i<=k;i++)
    {
        nkl p=q.top();q.pop();
        if(p.rem>k) break;
        else if(p.rem<i) return 0;

        ll nex=(p.now+mid)/b[p.id]+1;
        q.push((nkl){p.id,nex,p.now+mid});
    }

    return 1;
}

int main()
{
    scanf("%lld%lld",&n,&k);
    for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (ll i=1;i<=n;i++) scanf("%lld",&b[i]);

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

    printf("%lld\n",ans);

    return 0;
}