AT_abc413_c Large Queue 题解

Mindulle · 2025-07-05 20:58:01 · 题解

理解题意

可以看出题目有一个整数数列，要做一些操作，一种是插入，一种是删除，删除时还要求和。

插入

需要插入 c 个元素 x，并在数组末尾插入。

删除

需要删除数组前 k 个元素，并输出这 k 个元素的和。

解题思路

首先，看到删除是删除前面，插入是插入在末尾，自然想到了队列。我们可以用库中自带的队列，也可以手写。代码展示的是STL的队列。

但这题和模板队列稍有不同，它需要连续插入很多元素，删除很多元素，暴力显然是不行的，我们要考虑如何优化。

可以把队列改成一个结构体（因为这样比较方便），输入的时候把个数保存起来，删除的时候考虑如果 k \le 队首元素的个数，那么删完 k 个就删不了了，把个数减去 k 就行了，sum 加上 k 乘这个元素，这里 k 就直接变为 0 即可。否则直接删掉全部元素，k 减去这些元素的个数，sum 加上这个元素乘它的数量就行了。最后要注意一下数据范围就可以了。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{int times,num;};
queue<node>q;
signed main(){
  int t;
  scanf("%lld",&t);
  while(t--){
    int op;
    scanf("%lld",&op);
    if(op==1){
      int c,x;
      scanf("%lld%lld",&c,&x);
      q.push({c,x});
    }else{
      int k,sum=0;
      scanf("%lld",&k);
      while(!q.empty()&&k){
        if(q.front().times<=k){
          k-=q.front().times;
          sum+=q.front().times*q.front().num;
          q.pop();
        }else{
          q.front().times-=k;
          sum+=k*q.front().num;
          k=0;
        }
      }
      printf("%lld\n",sum);
    }
  }
  return 0;
}