XieNaoban's Blog
0%

2017 ACM Qingdao Online - Brute Force Sorting

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 3.3k 阅读时长 ≈ 3 分钟

2017 ACM-ICPC Asia Regional Qingdao Online - 1010 - Brute Force Sorting（HDU6215）

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1195 Accepted Submission(s): 309

Problem Description

Beerus needs to sort an array of N integers. Algorithms are not Beerus's strength. Destruction is what he excels. He can destroy all unsorted numbers in the array simultaneously. A number A[i] of the array is sorted if it satisfies the following requirements. 1. A[i] is the first element of the array, or it is no smaller than the left one A[i−1]. 2. A[i] is the last element of the array, or it is no bigger than the right one A[i+1]. In [1,4,5,2,3], for instance, the element 5 and the element 2 would be destoryed by Beerus. The array would become [1,4,3]. If the new array were still unsorted, Beerus would do it again. Help Beerus predict the final array.

Input

The first line of input contains an integer T (1≤T≤10) which is the total number of test cases. For each test case, the first line provides the size of the inital array which would be positive and no bigger than 100000. The second line describes the array with N positive integers A[1],A[2],⋯,A[N] where each integer A[i] satisfies 1≤A[i]≤100000.

Output

For eact test case output two lines. The first line contains an integer M which is the size of the final array. The second line contains M integers describing the final array. If the final array is empty, M should be 0 and the second line should be an empty line.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5
5
1 2 3 4 5
5
5 4 3 2 1
5
1 2 3 2 1
5
1 3 5 4 2
5
2 4 1 3 5

Sample Output

1
2
3
4
5
6
7
8
9
10
5
1 2 3 4 5 
0

2
1 2 
2
1 3 
3
2 3 5

Source

2017 ACM/ICPC Asia Regional Qingdao Online

Key

比赛时想不出怎么做，暴力模拟了一遍，果不其然TLE。。。。大佬对我表示很无奈。

大佬：不是让你这么模拟啊！！！

大佬提醒说用个审查队列维护，猛然醒悟。。。事后看了大佬的AC代码，又自己撸了一遍，终于AC了。（以及大佬的代码是真的优美）

用链表模拟，方便删除。关键点：模拟的时候用一个审查队列维护下一轮需要更新（可能删除）的点。每一轮删除都O(n)检查整个剩余序列肯定是不行的，把可能需要删除的点加入审查队列，每次只要检查队列里的每个元素即可。

哪些属于下一轮可能删除的点呢？上一轮删除的结点的左右结点。以及有一些小坑要注意。以下是我事后的AC的代码。

Code

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
#include<iostream>
#include<queue>
using namespace std;
const int Maxn = 100000 + 23;

struct Node {
	Node *l, *r;
	int v;
	Node(int _v, Node *_l) :v(_v), l(_l), r(nullptr) {}
};

int T, N;

queue<Node*> ToDel, ToChk;
Node *head;

Node *Del(Node *p) {
	Node *pl = p->l;
	Node *pr = p->r;
	pl->r = pr;
	pr->l = pl;
	delete p;
	return pl;
}

void Input() {
	cin >> N;
	head = new Node(0, nullptr);
	Node *now = head;
	int v;
	for (int i = 1; i <= N; ++i) {
		cin >> v;
		now->r = new Node(v, now);
		now = now->r;
	}
	now->r = new Node(Maxn, now);
}

void Output() {
	int num = 0;
	Node *i;
	for (i = head->r; i->v != Maxn; i = i->r) ++num;
	cout << num << '\n';

	for (i = head->r; i->v != Maxn; i = i->r) {
		delete i->l;
		cout << i->v << ' ';
	}
	delete i;
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin >> T;
	while (T--) {
		Input();

		for (Node *i = head->r; i->v != Maxn; i = i->r) {
			if (i->v < i->l->v || i->v > i->r->v) {
				ToDel.push(i);
			}
		}

		while (!ToDel.empty()) {
			do {
				Node *now = ToDel.front();
				ToDel.pop();
				Node *pre = now->l;
				Node *nxt = now->r;
				Del(now);
				if (pre->v != 0 && (ToChk.empty() || ToChk.back() != pre)) ToChk.push(pre);
				if (nxt->v != Maxn && (ToDel.empty() || ToDel.front() != nxt)) ToChk.push(nxt);
			} while (!ToDel.empty());

			while (!ToChk.empty()) {
				Node *now = ToChk.front();
				ToChk.pop();
				Node *pre = now->l;
				Node *nxt = now->r;
				if (now->v<pre->v || now->v>nxt->v) ToDel.push(now);
			}
		}

		Output();
	}
}