题解：CF1132D Stressful Training

· · 题解

upd 2024.11.8 手欠撤销了题解，所以更改了一些地方，主要关于无解判断和部分卡常

省流：一个写了双 \log 的人因为抢不到最优解，把复杂度优化到单 \log。

双 \log 解法

题目传送门

容易发现，答案具有单调性，考虑二分答案。

这样，问题变为已知充电量，求出是否存在方案，使得前 k 分钟都有电，并且单次复杂度要在 O(n\log n) 级别或以下。

但是如果维护每分钟的剩余电量，每分钟都更改，由于每台电脑消耗的速度不相同，每分钟为 O(n)，显然会超时，单次复杂度至少是 O(nk)。

考虑不维护每分钟电量，只维护从开始时可使用时间（包括所有充电后的可使用时间）。

如果我们先给剩余时间少（很快就会没电）的人充电，与先给剩余时间多（晚些时候会没电）的人充电：

  1. 如果我们给剩余时间多的人充电，导致剩余时间少的人没电了，那么显然得不偿失。

  2. 否则，因为充电量一直不变，所以先充电，后充电对答案没有影响，即先给剩余时间少的人充电没有负面影响，结果不变。

从以上两点看，我们选择剩余时间更短的人充电一定更优。

如何选择剩余时间最短的人？

暴力求这个点是 O(n) 的，考虑只有一个人被充电，而且一定是那个剩余时间最短的人，也就是只操作最值...这不是堆优化吗？

这样，对于每分钟，用堆维护所有人没电的时间，选择时间最短的，将其充电后重新放回堆里，时间复杂度为 O(\log{n})，单次检查复杂度为 O(k\log{n})。

总时间复杂度为 O((k+n)\log{n}\log{val})，val 为二分上界。

对于充电头来说，当然是功率越大越强，但是到达对于每个人都是只需一次充电的程度之后（即充一次就可以用到比赛结束），没有区别，所以答案上界（有解时）为 \max(b_i)\times k = 2 \times 10^{12}，并可以证明实际上比这个还小。如果二分后超过此值，则判断无解。

堆采用 STL 实现。

一些小优化：（单个加速 0.1 秒左右）

  1. 不需要再充电的就不用进堆了，反正再次充电也没用。
  2. 有了上一点优化后，当堆为空时，直接返回 true 就好了。
  3. 如果所有人的电池容量减去消耗速度都不够 k 分钟花的，直接返回 false。
  4. 每次 check 都新开一个堆，而不将原来的堆清空后使用。
  5. 开 C++20 O2。
  6. 快读。
  7. 由于此做法的空间复杂度小，可以把快读的 fread 一次读入的字符数量增加。

一些较大的优化

  1. 可以把初始堆记录下来，这样每次 check 时，建立 STL 堆的复杂度就从 O(n\log{n}) 变为 O(n)，总复杂度变为 O(k\log{n}\log{val})。
  2. 不用开 long long 的用 int 就行了。
  3. 将剩余的时间存起来，而不是单独计算，剩余时间用 int 而不是 double 存。
  4. 事实上，无解的情况可以 O(n+k) 判断，见下方代码。

代码：

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

constexpr int maxn=2e5+100;

#define ll long long

ll a[maxn],b[maxn];
ll n,m;
ll totb;
ll tote;

char buf[50000001];

inline char nc()
{
    static char *p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,30000000,stdin),p1==p2)?EOF:*p1++;
}

ll read()
{
    static char a=nc();
    while(!isdigit(a)){a=nc();}
    ll n=0;
    while(isdigit(a))
    {
        n=(n<<1)+(n<<3)+(a^48);
        a=nc();
    }
    return n;
}
//以上是快读

struct man
{
    ll a1,b1;int last;// a1 表示初始（包括充电后的）电量 ，b1 表示每分钟消耗电量
    //last表示从0时刻起可用时间
    //按整分钟算，14.01 分钟和 14.99 分钟一样，都是第 15 分钟没电（即可以忽略小数部分）
    bool operator <(const man tmp)const
    {
        return last>tmp.last;//注意 STL 是大根堆
    }
};
priority_queue<man> q;

bool check(ll x)
{
    if((totb-x)>tote/(double)(m-1))return false;//优化 3 
    priority_queue<man> q2=q;
    //大优化 1
    for(int i=0;i<m;i++)//第 i 到 i+1 分钟 
    {
        if(q2.empty())return true;//优化 2 
        man tmp=q2.top();
        //cout<<tmp.a1<<' '<<i<<'\n';
        q2.pop();
        if(tmp.last<i)return false;//已经有人电量为负了
        else if((tmp.a1+x)<tmp.b1*m)q2.push({tmp.a1+x,tmp.b1,(tmp.a1+x)/tmp.b1});
        //充电后重新入队，优化 1 
    }
    return true;// k 分钟后无事发生
}

int tmp_bucket[200001];

bool can_doit()
{
    for(int i=1;i<=n;i++)
    {
        if(a[i]<b[i]*m)tmp_bucket[a[i]/b[i]]++;
    //如果超过了 m 分钟，直接无视
    }
    for(int i=0;i<m;i++)
    {
        if(i)tmp_bucket[i]+=tmp_bucket[i-1];
        //防止越界
        if(tmp_bucket[i]>i+1)//这段时间内可以充电 i+1 次，如果有超过 i+1 个人要充电
            return false;//无解 
    }
    return true;
} 

signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        tote+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
        totb+=b[i];
    }
    for(int i=1;i<=n;i++)if(a[i]<b[i]*m)q.push({a[i],b[i],a[i]/b[i]});
    if(!can_doit())//无解 
    {
        cout<<-1;
        return 0;
    }
//预处理 check 时的初始堆
    ll l=-1,r=2e12,mid;
//二分区间要开大，左区间需要为 -1
    while(l<r-1)
    {
        mid=(l+r)>>1;
        if(check(mid)){r=mid;}
        else l=mid;
    } 
    cout<<r;
    return 0;
}

走向单 \log

我们发现，有了上述优化后，在堆中的人一定是可使用时长小于 k 的，且（从开始时）的可使用时长单调不减，而 k 较小，所以考虑用计数排序的思想。

我们用一个一维数组套 vector，用第一维来表示可使用时间（从开始时计算，下同），用第二维来表示所有的，这个时间没电的人。
每次从上一次的最小值开始，往后遍历 vector，找到最近一个有元素的 vector 并取出其的一个元素（实际使用时从后往前取以规避线性删除），判断合法性并将其充电后放到最新的位置，如果发现这次充电后不用再充电，则不做操作。

时间复杂度为 O((n+k)\log{val})。

如果跟双 \log 做法类似的去存储初始状态并每次复原，时间复杂度变为 O(k\log{val})，但是因为本题 n 和 k 同级，所以并不用这样做。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

constexpr int maxn=2e5+100;

#define ll long long

ll a[maxn],b[maxn];
ll n,m;
ll totb;
ll tote;

inline char nc()
{
    static char buf[30000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,30000000,stdin),p1==p2)?EOF:*p1++;
}

ll read()
{
    static char a=nc();
    while(!isdigit(a)){a=nc();}
    static ll n;n=0;
    while(isdigit(a))
    {
        n=(n<<1)+(n<<3);
        n+=(int)(a^48);
        a=nc();
    }
    return n;
}
//以上是快读

struct man
{
    ll a1,b1;int last;// a1 表示初始（包括充电后的）电量 ，b1 表示每分钟消耗电量
    //last表示从0时刻起可用时间
    //按整分钟算，14.01 分钟和 14.99 分钟一样，都是第 15 分钟没电（即可以忽略小数部分）
};
struct fm//find_max 的缩写
{
    vector<man> bucket[maxn];//桶 
    int now;//使用这个变量作为指针
    fm(){now=0;}
    void operator =(const fm tmp)
    {
        for(int i=tmp.now;i<=m;i++)
        {
            bucket[i]=tmp.bucket[i];
        }
        now=tmp.now;
    }
    inline bool empty()
    {
        while(!bucket[now].size()&&now<=m)now++;//跳过空桶
        return now==m+1;
    }
    inline man top()
    {
//由于每次调用前都会检查是否为空，所以不必再次清空
        return bucket[now].back();
    }
    inline void push(man tmp)
    {
        bucket[tmp.last].emplace_back(tmp);
    }
    inline void pop()
    {
        bucket[now].pop_back();
    }
}q,q2;

bool check(ll x)
{
    if((totb-x)>tote/(double)(m-1))return false;//优化 3 
    q2=q;
    for(int i=1;i<=m;i++)
    {
        if(q2.empty())return true;//优化 2 
        man tmp=q2.top();
        //cout<<tmp.a1<<' '<<i<<'\n';
        q2.pop();
        if(tmp.last<(i-1))return false;
        //已经有人电量为负了，注意这里是 i-1 ，是因为计算前 i-1 分钟而不是前 i 分钟 
        else if((tmp.a1+x)<tmp.b1*m)q2.push({tmp.a1+x,tmp.b1,(tmp.a1+x)/tmp.b1});
    }
    //充电后重新入队，优化 1 
    return true;// k 分钟后无事发生
}

signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        tote+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
        totb+=b[i];
    }
    for(int i=1;i<=n;i++)if(a[i]<b[i]*m)q.push({a[i],b[i],a[i]/b[i]});
//预处理 check 时的初始桶
    if(q.empty()){cout<<0;return 0;}//其实不仅处理了不用充电，而且重置了指针 
    ll l=-1,r=2e12,mid;
//二分区间要开大，左区间需要为 -1
    while(l<r-1)
    {
        mid=(l+r)>>1;
        if(check(mid)){r=mid;}
        else l=mid;
        //cout<<"Success\n";
    } 
    if(r==2e12)cout<<-1;//无解
    else cout<<r;
    return 0;
}

不知道是常数哪里过大了，时间反而是原来双 \log 的 1.5 倍，知道的可以私信。

附上错误指南：WA，TLE集