国外竞赛

BOI 2007 The Sound of Silence

Posted in 国外竞赛 on 五月 21st, 2010 by 纳米 – 3 Comments

题目大意：
给定n个数，求出所有满足以下条件片段的起始位置：片段长度为M、片段内最大数和最小数的差小于给定的c。

解题报告：
这道题是《1D/1D动态规划优化初步》里面的例题，其实跟动态规划没啥关系，只是用到了一个单调队列优化。这个问题实质就是求每一个片段中最大值和最小值。因为求最小值和最大值本质是一样的，所以以最小值为例：
维护一个单调不下降的队列，每次遇到一个数，首先在队列头，若存在位置在这个数m个位置之前的元素，删掉。然后，在队列尾检查，若存在比该数大的元素，删掉。再在队列尾加入该数。这样，我们就得到了一个单调不下降序列。容易知道，队列头的元素就是以该数结尾的片段中最小的数字。
求出了每个片段中的最大值和最小值，问题就解决了。每个数只可能进、出一次队列，所以时间复杂度为O(n)。

我很恶心地使用了Class来实现这个代码。

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

#include <stdio.h>
 
const char IN_FILE_NAME[] = "sound.in";
const char OUT_FILE_NAME[] = "sound.out";
 
const int maxn = 1000005, maxm = 10005;
int n, m, c, data[maxn];
class Queue {
	private:
		int num[maxn], pos[maxn], head, last;
	public:
		Queue() {
			head = 1;
			last = 0;
		}
		bool Empty() {
			return head > last;
		}
		int GetFirstNum() {
			return num[head];
		}
		int GetFirstPos() {
			return pos[head];
		}
		int GetLastNum() {
			return num[last];
		}
		void DelFirst() {
			++head;
		}
		void DelLast() {
			--last;
		}
		void Insert(int n, int p) {
			num[++last] = n;
			pos[last] = p;
		}
} qmin, qmax;
bool answer[maxn];
 
int input() {
	FILE *fin = fopen(IN_FILE_NAME, "r");
	fscanf(fin, "%d%d%d", &n, &m, &c);
	for (int i = 1; i <= n; ++i)
		fscanf(fin, "%d", &data[i]);
	fclose(fin);
	return 0;
}
 
int work() {
	for (int i = 1; i < m; ++i) {
		while (!qmin.Empty() && qmin.GetLastNum() > data[i])
			qmin.DelLast();
		qmin.Insert(data[i], i);
		while (!qmax.Empty() && qmax.GetLastNum() < data[i])
			qmax.DelLast();
		qmax.Insert(data[i], i);
	}
	for (int i = m, j = 1; i <= n; ++i, ++j) {
		while (!qmin.Empty() && qmin.GetFirstPos() < j)
			qmin.DelFirst();
		while (!qmin.Empty() && qmin.GetLastNum() > data[i])
			qmin.DelLast();
		qmin.Insert(data[i], i);
		while (!qmax.Empty() && qmax.GetFirstPos() < j)
			qmax.DelFirst();
		while (!qmax.Empty() && qmax.GetLastNum() < data[i])
			qmax.DelLast();
		qmax.Insert(data[i], i);
		answer[j] = qmax.GetFirstNum() - qmin.GetFirstNum() <= c;
	}
	return 0;
}
 
int output() {
	FILE *fout = fopen(OUT_FILE_NAME, "w");
	bool is_ok = false;
	for (int i = 1; i <= n; ++i)
		if (answer[i]) {
			fprintf(fout, "%d\n", i);
			is_ok = true;
		}
	if (!is_ok)
		fprintf(fout, "NONE\n");
	fclose(fout);
	return 0;
}
 
int main() {
	input();
	work();
	output();
	return 0;
}