自动搬运

查看原文

来自洛谷，原作者为

	chlchl AFOed.

搬运于2025-08-24 22:30:30，当前版本为作者最后更新于2021-06-08 15:50:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

题目传送门

建议看完题不会再来看题解，不要一拿到题就往题解区狂奔。

简单来说，这道题的意思就是：有一个队列，里面有 n 个元素。现在有 m 个指令，每条指令只能是下面三种的其中一种：

1. 将队列里所有元素的值增加 x.
2. 将队列里所有元素的值减少 x.
3. 输出队列里值在 $\left[k, -k\right]$ 之间的元素个数。

而且，如果在某一轮，某个元素的值超出了这个给定范围，它就不会再次回到队列中（可以理解为被淘汰了）。

思路

题目已经疯狂地暗示我们了，这道题用的是队列。输入元素后先对其进行排序。接着，对于每个指令1和指令2，循环判断每一个元素 $a_i$ 在加上或减去 x 后是否在合法区间内。如果不是，就弹出队列。对于每个指令3，输出此时队列长度即可（STL 大法好！）。

用 STL 的 OIer 们请注意：

因为这道题两头都要判断，也就是说，有可能会在尾部弹出。所以，此时要用到 deque，俗称双向队列。

不知道双向队列的可以点这里。

一些小坑

这题坑比较少，但如果没注意还是会丢分。

• 输入数据不保证 $a_i$ 升序，所以需要进行排序。
• 指令3不需要输入 x，所以不能直接将 op 和 x 一起输入。
• 五年 OI 一场空，不开 long long 见祖宗，一定要注意数据范围，本题需要用 long long。

代码

代码实现难度也不大，我是个很懒的人，所以用的是 STL 实现队列。其他题解里也有很多手写队列的，大家也可以去看看。

$Code$：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll N = 300000 + 10;
ll n, m, k, op, x, tot, a[N];
//tot记录目前一共向正方向移动了多少个单位，可以是负数（负数代表向反方向移动） 
deque<ll> q;//定义双向队列 

int main(){
	cin >> n >> m >> k;
	for(ll i=1;i<=n;i++)	cin >> a[i];//需要另开一个数组输入，因为要排序 
	sort(a + 1, a + 1 + n);//排序 
	for(ll i=1;i<=n;i++)	q.push_back(a[i]);//进队 
	for(ll i=1;i<=m;i++){
		cin >> op;
		if(op == 3)	cout << q.size() << endl;//输出队列长度，也就是元素个数 
		else if(op == 1){
			cin >> x;
			tot += x;//刷新tot 
			while(!q.empty()){
				ll v = q.back();
				if(v + tot > k)	q.pop_back();//如果此埴轮移动完超过k，就被淘汰了 
				else	break;
			}
		}else if(op == 2){
			cin >> x;
			tot -= x;//刷新tot 
			while(!q.empty()){
				ll v = q.front();
				if(v + tot < -k)	q.pop_front();//如果此埴轮移动完小于-k，也会被淘汰 （从队头弹出） 
				else	break;
			}
		}
	}
	return 0;
}

本篇题解到此结束，如果对你有收获别忘了点赞哦！有什么问题也可以在评论区提出，作者很乐意为你解答。