算法题整理——队列

发表于 | 分类于 |

队列作为最基本的数据结构之一，有着广泛的应用。C++的queue头文件里有着现成的队列模板，可以实现队列的多种基本操作。此外，有时需要提高效率，可能要自己去用数组模拟一个循环队列——一个数组，两个指针，用取模意义下的加法作为指针加一

在普通的队列之外，还有队头队尾都能插入的双端队列，每次插入后都会排好序，按数值大小顺序而非入队顺序出队的优先队列等变种队列

UVa210_Concurrency Simulator

题意

模拟n个程序的并行执行（按输入顺序编号为1~n），每个程序包含不超过25条语句，一共有五种，分别是

var = constant（赋值）

print var（打印）

lock和unlock（锁定和解除）

end（结束）

变量都是用单个小写字母表示的，初始值均为0，为所有程序所公有，常数都是小于100的整数。

每个时刻只能有一个程序处于运行态，其他程序处于等待态，位于等待队列中。以上的五种语句需要执行的时间分别为t1，t2，t3，t4，t5，但运行态的程序每次运行时间最多为Q（称之为配额），当一个程序的配额执行完毕之后，把它当前的语句（如果没执行完）执行完毕之后放入等待队列，然后处理机会从等待队列的队首取出一个程序继续执行。初始的等待队列包含按照输入顺序的n个程序。

lock语句的作用是申请对变量的独占访问，如果一个程序执行了lock语句，其他程序一旦想要执行lock指令，就会马上被放入阻止队列的尾部（没有用完的配额就浪费掉了），等到最初执行lock的程序执行完unlock指令，处于阻止队列的队首的程序会被放入等待队列的队首。

输入n，t1~t5，Q以及n个程序，按照时间顺序输出所有print语句的结果。

思路

需要解决的问题有：

输入方面，需要存储t1~t5，Q，n的值，以及程序语句。笔者对于程序语句的存储方法是：把所有的程序语句按顺序存储在一个数组p里，一行一行地存，额外设置一个程序指针cur，对于i号程序，cur[i]就是其下一条语句的地址。

调度时，采用循环数组模拟队列，waitq和stopq分别作为等待队列和阻止队列，设置两个指针，队列中的内容就是程序的编号。这样，调度时，先取被调度的程序编号，再根据编号去cur数组中取指令地址。调出程序时，需要保存现场，即更新cur数组中当前指令的地址。

设置values数组，大小为26，haslocked表示是否已经有程序执行了lock指令。在指令执行时，根据不同的指令去进行不同的操作，如果是赋值指令，就去修改values数组的值，如果是输出，就输出相应的值，如果是lock，则去看haslocked变量是否为1，若为1，说明已经有程序执行了lock，则停止当前程序并且将其置入阻止队列，若没有则把它设置为1。对于unlock，把haslocked变量设置为0，并且若阻止队列里有程序，把它插入到等待队列的首部。并且每执行一条指令都要判断配额是否用完。

由于本题是多组输入，所以要注意在每次测试完一组之后进行重新初始化，包含变量，程序，队列和其指针等等的初始化。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<string>
#include<queue>
#include<cstring>
using namespace std;

int n=3;
int t[5];
int Q;

int values[26];

int haslocked;

char p[1005][10];

int cur[100];

int waitq[100];
int stopq[100]; 
int waitq_front;
int waitq_rear;
int stopq_front;
int stopq_rear;

void runprogram()
{
	haslocked=0;
	memset(values,0,sizeof(values));
	int pro;
	while(waitq_front!=waitq_rear)
	{
		pro=waitq[waitq_front];
		waitq_front=(waitq_front+1)%100;
		int timelast=Q;
		int finish=0;
		int c=cur[pro];
		while(timelast>0)
		{
			char* ins=p[c];
			switch (ins[2])
			{
				case '=':
					timelast-=t[0];
					values[ins[0]-'a']=ins[5]?ins[4]*10+ins[5]-'0'*11:ins[4]-'0';
					break;
				case 'i':
					timelast-=t[1];
					printf("%d: %d\n",pro+1,values[ins[6]-'a']);
					break;
				case 'c':
					timelast-=t[2];
					if(haslocked)
					{
						finish=1;
						stopq[stopq_rear]=pro;
						stopq_rear=(stopq_rear+1)%100;
					}
					else haslocked=1;
					break;
				case 'l':
					timelast-=t[3];
					haslocked=0;
					if(stopq_rear!=stopq_front)
					{
						waitq_front=(waitq_front-1)%100;
						waitq[waitq_front]=stopq[stopq_front];
						stopq_front=(stopq_front+1)%100;
					}
					break;
				case 'd':
					finish=1;
					break;
			}
			if(finish)break;
			++c;
		}
		cur[pro]=c;
		if(!finish)
		{
			waitq[waitq_rear]=pro;
			waitq_rear=(waitq_rear+1)%100;
		}
	}
}

int main()
{
	int N;
	scanf("%d",&N);
	while(N--)
	{
		scanf("%d %d %d %d %d %d %d\n",&n,&t[0],&t[1],&t[2],&t[3],&t[4],&Q);
		waitq_front=0;
		waitq_rear=0;
		stopq_front=0;
		stopq_rear=0;
		int j=0;
		for(int i=0;i<n;++i)
		{
			cur[i]=j;
			gets(p[j]);
			while(p[j++][2]!='d')gets(p[j]);
			waitq[i]=i;
		}
		waitq_rear=n;
		runprogram();
		if(N)printf("\n");
	}
	return 0;
}

POJ2259_Team Queue

描述

这道题的描述感觉很像生活中排队的场景：

假设食堂正在排队打饭，这时，一个学生来了，发现队伍里面有他认识的人，他选择插队可以打饭更快一点。如果没有，他就会排在队伍的最后面。

本题的描述是这样的：把一些数字分成若干组，然后维护一个队列。对于每次入队操作ENQUEUE x，如果发现队伍里有和x同组的数，就把x放在这个数的后面（显然如果有多个同组的数，它们肯定都相邻，这时x就放在这一组的最后面）。如果没有，x排在队尾。

对DEQUEUE操作，只需要弹出队头并输出即可。

数据范围

分组数目 t < 1000

每组数字个数 n < 1000

数字大小在1 ~ 999999之间

思路

首先，数字范围很小，我们直接使用一个数组来存储每个数属于哪个小组，这样查找效率是O(1)。

可以用队列的数组来模拟一个队列的队列，每个小组的元素排在一起构成一个队列，然后队列之间又构成了新的队列。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e3 + 5;

int pos[N];
int belong[N * N];
queue<int> q[N];
int strt;
int ed;

int main(){
	int t;
	scanf("%d", &t);
	int k = 0;
	while(t){
		if(k) printf("\n");
		printf("Scenario #%d\n", ++k);
		
		memset(belong, 0, sizeof(belong));
		memset(pos, -1, sizeof(pos));
		
		for(int i = 0; i < N; ++i){
			while(!q[i].empty()) q[i].pop();
		}
		
		strt = 0;
		ed = 0;
		
		for(int i = 0; i < t; ++i){
			int n;
			scanf("%d", &n);
			for(int j = 0; j < n; ++j){
				int elem;
				scanf("%d", &elem);
				belong[elem] = i;
			}
		}
		
		char input[100];
		scanf("%s", input);
		while(input[0] != 'S'){
			if(input[0] == 'E'){
				int elem;
				scanf("%d", &elem);
				if(pos[belong[elem]] != -1){
					q[pos[belong[elem]]].push(elem);
				}else{
					pos[belong[elem]] = ed;
					q[pos[belong[elem]]].push(elem);
					ed = (ed + 1) % N;
				}
			}else{
				int elem = q[strt].front();
				printf("%d\n", elem);
				q[strt].pop();
				if(q[strt].empty()){
					pos[belong[elem]] = -1;
					strt = (strt + 1) % N;
				}
			}
			scanf("%s", input);
		}
		 
		scanf("%d", &t);
	}
	return 0;
}

CH1202_蚯蚓

描述

蛐蛐国里现在共有n(1 ≤ n ≤ 10^5 )只蚯蚓，第i只蚯蚓的长度为a_i(a_i ≤ 10^8)，所有蚯蚓的长度都是非负整数，即可能存在长度为0的蚯蚓。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只，将其切成两段。若有多只最长的，则任选一只。神刀手切开蚯蚓的位置由有理数p(0 < p < 1) 决定。一只长度为x的蚯蚓会被切成两只长度分别为px和x - px的蚯蚓。

特殊地，如果这两个数的其中一个等于0，则这个长度为0的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加一个非负整数q(q ≤ 200)。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m(m ≤ 7e6)秒才能到来。

蛐蛐国王希望知道这m秒内的战况。具体来说，他希望知道：

m秒内，每一秒被切断的蚯蚓被切断前的长度，共有m个数。

m秒后，所有蚯蚓的长度，共有n + m个数。

思路

一上来做成了优先队列：

取初始状态下所有蚯蚓的长度，建立优先队列。

对于每一秒，取出堆顶，切断，放入两个新生蚯蚓。

然而，没有被切到的蚯蚓会生长，我们不能逐个加q，只能这样处理：

取出的堆顶元素len，先加上q * i - q才是真正的长度。

切断后形成的两个新生蚯蚓，求出它们在初始状态下的等价长度，即减去q * i。

最后输出所有蚯蚓的长度需要逐个出队。

m次入队，每次复杂度是O(log(n + i))，i表示当前是第几次入队，总复杂度不大于mlogm，出队的复杂度则是m次logm。

所以优先队列的复杂度是O(mlogm)。

这题如果观察到位了，还有普通队列的做法：

由于蚯蚓是从大到小等比例切断的，所以如果把最初的蚯蚓放在有序的队列，被切断的两个新生蚯蚓各自按顺序放入其他两个队列的话，我们能够得到3个有序队列，这样，每轮切蚯蚓，我们比较三个队列的队头找出最大的即可。

所以只需要最初排个序，复杂度是O(nlogn)。

这个题n的规模远比m小，所以第二种方法更好一些。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

long long n, m, q, u, v, t;

int firstcon, secondcon;

int main(){
	//freopen("input", "r", stdin);
	//freopen("testoutput", "w", stdout);
	scanf("%lld %lld %lld %lld %lld %lld", &n, &m, &q, &u, &v, &t);
	vector<long long> qu;
	long long temp;
	for(int i = 0; i < n; ++i){
		scanf("%lld", &temp);
		qu.push_back(temp);
	}
	
	firstcon = 0;
	secondcon = 1;
	
	queue<long long> fq;
	queue<long long> sq;
	queue<long long> tq;
	
	sort(qu.begin(), qu.end());
	
	//for(int i = qu.size() - 1; i >= 0; --i) printf("qu = %d\n", qu[i]);
	
	for(int i = qu.size() - 1; i >= 0; --i) fq.push(qu[i]);
	
	for(long long i = 1; i <= m; ++i){
		int flag = 0;
		
		long long len = 0x8000000000000000;
		if(!fq.empty() && len < fq.front()) len = fq.front(), flag = 1;
		if(!sq.empty() && len < sq.front()) len = sq.front(), flag = 2;
		if(!tq.empty() && len < tq.front()) len = tq.front(), flag = 3;
		
		//printf("fq %d\n", fq.front());
		
		len += q * (i - 1);
		
		//printf("len = %d\n", len);
		
		if(flag == 1) fq.pop();
		if(flag == 2) sq.pop();
		if(flag == 3) tq.pop();
		
		if(i % t == 0){
			if(firstcon) printf(" %lld", len);
			else{
				printf("%lld", len);
				firstcon = 1;
			}
		}
		sq.push(len * u / v - q * i);
		tq.push(len - len * u / v - q * i);
	}
	
	printf("\n");
	
	while(!fq.empty() || !sq.empty() || !tq.empty()){
		int flag = 0;
		
		long long len = 0x8000000000000000;
		if(!fq.empty() && len < fq.front()) len = fq.front(), flag = 1;
		if(!sq.empty() && len < sq.front()) len = sq.front(), flag = 2;
		if(!tq.empty() && len < tq.front()) len = tq.front(), flag = 3;
		
		if(flag == 1) fq.pop();
		if(flag == 2) sq.pop();
		if(flag == 3) tq.pop();
		
		if(secondcon % t == 0){
			if(secondcon > t) printf(" %lld", len + m * q);
			else{
				printf("%lld", len + m * q);
			}
		}
		++secondcon;
	}
	printf("\n");
	
	return 0;
}

CH1201_最大子序和

描述

输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得整个序列的和最大。

数据范围

1 < n,m < 3e6

思路

首先求出前缀和数组，把[i,j]的子序列和转换为前缀和数组a[j]-a[i]的值。

假设我们取了一个子序列，其终点为j，那么起点可以选择在j-m+1至j的任何位置。显然最好的位置是这些中前缀和最小的。

我们能不能一直存储着某个点前m个位置中前缀和最小的位置呢？答案是否定的，因为我们会不停地向后更新，因为题目中限定了子序列的长度，在终点不断向后遍历的情况下，前缀和最小的位置很有可能会改变。

那么，考虑前缀和最小的位置会怎么变。假设我们现在已知前缀和最小的位置是i，终点是j，j向后移动了一格变成j+1，那么j这个位置成为新的可选范围。如果j这个位置前缀和比i更小，显然我们会把i更新为j，j的位置前缀和如果比i大，似乎我们什么都不需要做。

但考虑j一直在后移导致i可能会出界，假设j后移之后正好更新了i，显然我们不需要考虑i出界的问题，因为已经把i抛弃了。但如果j后移之后无法更新i，那么我们需要在i+1到 j这个范围内重新寻找最小值。

换句话说，我们需要存储i之后稍微比i的前缀和大一点的数。而且需要保证在i+1到j这个区间里，没有一个数比它小。

假设这个数是k1，那么显然i到k1之间的数字是不需要的。

考虑到k1也有可能会出界，我们继续存储k1之后前缀和稍微比k1的前缀和大的数，假设这个位置是k2，那么k1到k2之间的数也是不需要的。

所以我们的策略是维护数组前缀和的单调双端队列，如果后面来了一个比队尾小的数，就一直从队尾出队直到队伍里没有比它更大的。如果来了一个比队尾大的数，直接入队。

同时记录队列里数的下标，以便于判断队列长度有没有出界。

我们的策略是：

判断是否出界，若是，队头出队。

使用队头和接下来的元素计算出新的子序列和。

把队尾大于等于接下来元素的都出队，然后把新元素入队。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <queue>

using namespace std;

const int N = 3e6 + 5;

int a;

int main(){
	int n, m;
	long long temp, ret = 0x8000000000000000;
	deque<long long> qv;
	deque<int> qp;
	scanf("%d %d", &n, &m);
	a = 0;
	qv.push_back(0);
	qp.push_back(0);
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &temp);
		//printf("%lld\n", qv.front());
		a += temp;
		if(i - qp.front() > m){
			qv.pop_front();
			qp.pop_front();
		}
		ret = ret < a - qv.front() ? a - qv.front() : ret;
		while(!qv.empty() && qv.back() >= a){
			qv.pop_back();
			qp.pop_back();
		}
		qv.push_back(a);
		qp.push_back(i);
	}
	printf("%lld\n", ret);
	return 0;
}

BZOJ2457_双端队列

描述

Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。

Sherry手头能用的工具就是若干个双端队列。

她需要依次处理这N个数，对于每个数，Sherry能做以下两件事：

1新建一个双端队列，并将当前数作为这个队列中的唯一的数；

2将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。

数据范围

1 < N < 2e6

思路

这题是我看着题解做的。

由于最后把队列排序之后可以得到一个非降的序列，说明这些队列把最终排序完成的数组分成了若干个连续的子序列，队列里面的内容就是子序列的内容。

我们考虑某个队列q，其内部的元素为A1,A2,A3,…,An，显然它们是非降的，再考虑队列的形成过程：首先，必然有一个元素Ak先进入了队列q，然后，对于A1,A2,…,Ak-1，它们肯定是从Ak-1开始依次入队直到A1最后一个入队。同理，对于Ak+1,…,An，它们的入队顺序是Ak+1依次入队到An。

那么，在未排序之前，A1到An在原数组里的下标肯定是这样的：从A1的下标开始，下标递减，直到Ak递减到最小值，再到An的下标递增。

所以，我们对数组排序的同时保留它们在原数组中的下标，在新数组中用贪心的思路来尽可能地把新数组划分成原下标先增后减的子序列。

那么，对于原数组中出现了好几次的元素，我们需要按情况进行分类讨论。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2e5 + 5;

pair<int, int> a[N];

int n, ret;

int main(){
	ret = 0;
	
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &a[i].first);
		a[i].second = i;
	}
	sort(a, a + n);
	
	/*for(int i = 0; i < n; ++i){
		printf("%d %d\n", a[i].first, a[i].second);
	}*/
	
	int up = 1;
	int last = 0x7fffffff;
	
	for(int i = 0; i < n;){
		int j = i;
		while(a[j].first == a[i].first && j < n) ++j;
		--j;
		if(up){
			if(a[i].second > last){
				last = a[j].second;
			}else{
				up = 0;
				++ret;
				last = a[i].second;
			}
		}else{
			if(a[j].second < last){
				last = a[i].second;
			}else{
				up = 1;
				last = a[j].second;
			}
		}
		i = j + 1;
	}
	
	printf("%d\n", ret);
	
	return 0;
}