P8755 [蓝桥杯 2021 省 AB2] 负载均衡

原题链接

我曾经写题时有个疑惑，那就是会不会算力恢复之后大于最大算力？
其实不会，把消耗的算力想象成占领，恢复算力想象成撤离，不管怎么恢复，领地都是那个领地。

#include<bits/stdc++.h>
using namespace std;
int power[200005]={0};
struct unit
{
    int when,who,recover;
    //分别代表什么时候，哪台电脑，恢复多少算力
}pile[200005];//按恢复时刻进行堆排序
int len=0;
void out()//堆弹出堆顶元素，属于模板操作
{
    swap(pile[1],pile[len--]);
    //把最后一个元素放到堆顶，原来的堆顶放到最后删除，然后开始下沉操作
    int now=1;
    while(2*now<=len)
    {
        int son=2*now;//代表左儿子
        if(son+1<=len&&pile[son+1].when<pile[son].when)son++;
        //如果有右儿子并且右儿子比左儿子小
        if(pile[son].when<pile[now].when)
        {//和更小儿子交换
            swap(pile[son],pile[now]);
            now=son;
        }
        else break;//代表下沉完毕
    }
}
void in(int now)//堆放入新元素，也是属于模板操作
{
    while(pile[now].when<pile[now/2].when&&now>=2)
    {
        swap(pile[now],pile[now/2]);
        now/=2;
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&power[i]);//代表电脑的最大算力
    for(int i=1;i<=m;i++)
    {
        int t,cp,last,consume;
        scanf("%d%d%d%d",&t,&cp,&last,&consume);
        while(len>=1&&pile[1].when<=t)
        {
            power[pile[1].who]+=pile[1].recover;
            out();
        }
        if(consume>power[cp])  printf("-1\n");//如果该操作所需算力大于该操作所需电脑的当前算力
        else
        {
            printf("%d\n",power[cp]-consume);//剩余算力
            len++;
            pile[len].when=t+last;//恢复时刻
            pile[len].who=cp;//恢复的电脑
            pile[len].recover=consume;//恢复的算力值
            in(len);
            power[cp]-=consume;
        }
    }
    return 0;
}