题解：CF1132D Stressful Training

0Io_oI0 · 2025-06-22 18:54:18 · 题解

解题思路就是，如果确定 p 判断是否存在方案，则每次贪心选择最早电量小于 0 的电池 u 充电总是最优的。否则考虑如果存在另一个充电方案 T' 在当前时刻给 u'\ne u 充电，那么假设 T' 下一次给 u 充电是 t' 时刻，交换当前时刻和 t' 时刻的充电操作总是合法的。

于是可以二分 p，每次按上述贪心判断是否存在方案。判断可以使用优先队列加速，时间复杂度为 O(n\log ^2n)。

上代码！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>pli;
namespace fastIO{char *p1,*p2,buf[100000];
    #define R register
    #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
    inline void read(ll&n){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}inline void read(string&s){s="";char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}inline void write(ll x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}inline void write(const string&s){for(R ll i=0;i<(int)s.size();i++){putchar(s[i]);}}inline void write(const char&c){putchar(c);}
}using namespace fastIO;
const ll INF=2e12,MAXN=2000010;
ll a[MAXN],b[MAXN],cnt[MAXN],last[MAXN],n,k;
bool check(ll x){
    priority_queue<pli,vector<pli>,greater<pli> >q;
    for(R ll i=0;i<n;i++){
        cnt[i]=0;
        if(a[i]>=b[i]*k)last[i]=-1;
        else{
            ll d=a[i]/b[i]+1;
            if(d<k) {
                last[i]=d;
                q.push({d,i});
            }
            else last[i]=-1;
        }
    }
    for(R ll j=0;j<k;j++){
        while(!q.empty()){
            pli top=q.top();
            ll d=top.first,i=top.second;
            if(d!=last[i]){
                q.pop();
                continue;
            }
            if(d<=j)return 0;
            break;
        }
        if(q.empty())break;
        pli top=q.top();
        q.pop();
        ll i=top.second;
        cnt[i]++;
        ll charge=a[i]+x*cnt[i]-b[i]*(j+1);
        if(charge<0)return 0;
        ll tot=a[i]+x*cnt[i],new_;
        if(tot>=b[i]*k)new_=k;
        else new_=(tot/b[i])+1;
        if(new_<k){
            last[i]=new_;
            q.push({new_,i});
        }
        else last[i]=-1;
    }
    return 1;
}
signed main(){
    read(n);
    read(k);
    for(ll i=0;i<n;i++)read(a[i]);
    for(ll i=0;i<n;i++)read(b[i]);
    ll l=0,r=INF;
    while(l<r){
        ll mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(l>=INF)puts("-1");
    else write(l);
    return 0;
}

亲测可过，请勿抄袭。

注：作者的代码好像常数有点大，所以加了快读快写，不加快读快写的话，后面几个点可能会被卡。