AT_abc379_d 题解

ikunTLE · 2024-11-09 22:01:43 · 题解

题目传送门

思路

首先，不难考虑到 \mathcal{O}(Q^2) 的暴力解决方案：每一次操作 2 将所有的植物都增加 T；操作 3 挨个统计高度超过 H 的植物数量。

然后，想到操作 2 中可以增加一个变量控制增长的高度 h，将操作 2 的时间复杂度降至 \mathcal{O}(1)。此后要使操作 1 的初始高度为 0，就要将其赋值为 -h。

最后，使用优先队列降低复杂度。在操作 3 中，每次都删到比 H 低为止。由于所有的植物数量不会超过 Q，故总时间复杂度为 \mathcal{O}(Q\log Q)，可以通过此题。

注意事项

• 不开 long long 见祖宗。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
priority_queue<int/*,vector<int>,greater<int>*/>pq;
signed main(){
    int q=read(),h=0;
    while(q--){
        int op=read();
        if(op==1)
            pq.push(-h);
        else if(op==2)
            h+=read();
        else{
            int x=read(),ans=0;
            while(!pq.empty()){
                int temp=pq.top();
                if(temp+h>=x)
                    ++ans,pq.pop();
                else break;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}