洛谷P7505

洛谷P7505题解

题目信息：

题目传送门：https://www.luogu.com.cn/problem/P7505
知识点：队列，排序，模拟。

题目简述：

一个队列，里面有 n 个元素。有 m 个指令
命令有三种：

• 所有元素的值加 x
• 所有元素的值减 x
• 输出队列里值在 [k,−k] 之间的元素个数

运动过程中，如果元素值超过边界，就无法回到队列中了

注意，数据规模 1≤n,m≤300000，1≤k,x≤2000000000.

题目分析：

1.首先最直观的思路，用数组存每个人的位置，每次运动遍历判断是否越界即可。但是很显然这会超时。
2.优化，可以发现这组数如果进行排序，判断是否越界可以只关注两端即可
因此数据结构用双向队列。
双向队列的实现可以用STL中的deque,本题解选择用数组直接模拟

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 300000 + 5;
int n, m;
ll k,cnt;
ll que[maxn];
ll p, q;//模拟双向队列的两端


int main() {
	scanf("%d %d %lld", &n, &m, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &que[cnt++]);
	}
	sort(que, que + cnt);//升序
	p = 0; q = cnt - 1;

	int flag;
	ll dx, sum = 0;
	for (int i = 0; i < m; i++) {
		scanf("%d", &flag);
		if (flag == 1) {
			scanf("%lld", &dx);
			sum += dx;
			while (q >= p && que[q] + sum > k) q--;
		}
		else if (flag == 2) {
			scanf("%lld", &dx);
			sum -= dx;
			while (p <= q && que[p] + sum < -k) p++;
		}
		else if (flag == 3) printf("%lld\n", q - p + 1);

		//printf("xx%lld %lld %lld ", sum, p, q);   
		//printf("\n");
	}
}

---

最后