题解：AT_abc379_d [ABC379D] Home Garden

IGA_Indigo · 2024-11-10 08:41:24 · 题解

题目大意

给定 Q 次操作。

• 操作 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;
  }