题解:AT_abc379_d [ABC379D] Home Garden
IGA_Indigo · · 题解
题目大意
给定
- 操作 1:新建一个花。
- 操作 2:所有现有的花长高
t 长度。 - 操作 3:去除所有长度大于等与
h 的花,输出去除的数量。大体思路
建立一个大根堆,记录当前花种植时的时间
sum ,存入优先队列的是-sum ,进行操作 2 的时候只需要sum=sum+t 即可。操作 3 时遍历大根堆,如果其记录的时间(负值)加上sum 大于等于h 就除掉并累加。Code
#include<bits/stdc++.h> using namespace std; long long read(){ long long x=0,f=1; char 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; } void write(long long x){ if(x<0){ putchar('-'); x=-x; } if(x>9){ write(x/10); } putchar(x%10+'0'); return ; } priority_queue<long long> q; int main(){ int Q=read(); long long sum=0; while(Q--){ int cz=read(); if(cz==1){ q.push(-sum);//加入新花 } if(cz==2){ long long x=read(); sum+=x;//增加 sum } if(cz==3){ long long k=read(); int ans=0; while(!q.empty()){//遍历下大根堆 if(q.top()+sum>=k){ q.pop(); ans++; } else{ break ; } } write(ans);//输出累加的答案 puts(""); } } return 0; }