P7505 小小的埴轮兵团 题解
chlchl
·
·
题解
题目描述
题目传送门
建议看完题不会再来看题解，不要一拿到题就往题解区狂奔。
简单来说，这道题的意思就是：有一个队列，里面有 n 个元素。现在有 m 个指令，每条指令只能是下面三种的其中一种：
- 将队列里所有元素的值增加 x.
- 将队列里所有元素的值减少 x.
- 输出队列里值在 \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 实现队列。其他题解里也有很多手写队列的，大家也可以去看看。
```cpp
#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;
}
```
本篇题解到此结束，如果对你有收获别忘了点赞哦！有什么问题也可以在评论区提出，作者很乐意为你解答。