ABC 379 D - Home Garden（队列+前缀和）

传送门https://atcoder.jp/contests/abc379/tasks/abc379_d

题目大意

解题思路

这道题如果暴力的话，时间的瓶颈是在第二个操作。

可以发现第二个操作主要会增加植物的时间。

所以，可以想着做一个时间的前缀和。

设  表示第  次操作的时间前缀和；

然后，对于第一个操作，我们直接将植物入队；

对于第二个操作，改变 ；

对于第三个操作，让满足时间的植物出队，并统计（植物的时间可以由前缀和在  的时间求出）

代码

注意，要开 long long。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int op,x;
int s[200001];
int q[200001];
int head=1,tail=0;
int ans;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;int i=0;while(t--){cin>>op;i++;if(op==1){q[++tail]=i-1;s[i]=s[i-1];}if(op==2){cin>>x;s[i]=s[i-1]+x;}if(op==3){cin>>x;ans=0;s[i]=s[i-1];while(head<=tail&&s[i]-s[q[head]]>=x){head++;ans++;}cout<<ans<<endl;}}
}