Stack Sorting
Stack Sorting
写出来一个玄学的做法。。。。
题目来源: Codeforces
证明
题目要求的是令一个数组stack-sortable,也就是说这个数组可以通过一个栈中转从而变成非严格递增的有序数列。
那么我们就看一看一下这样的数组需要满足什么样的条件：
对于某一个数，因为当它在栈中被取出时所有比它小的数一定已经被取出了，所以所有比它小的数在栈中一定在它上面或者已在它进栈前出栈。并且所有比它大的数只能在它下面或者未被取出。
所以，对于某一个数x，所有比她小的数必须满足下面两种情况之一：
- 在它的左面；
- 在它的右面并且从这个数到
x之间的所有数都比x小。
若我们用区间来表示，那么一个stack-sortalbe的数列中对于每一个x都满足以下形式(每个项的位置不能改变)： \[ x + [1,x-1] + [x+1,n] \]
那么，由于题目中已经给出了k个数，所以我们可以推断这k个数是否满足条件。
实现
我们要维护一个式子，其中包含数字与区间。初始时该式子中无数字，只有一个区间$ [1,n] $。
然后我们每读入一个数，就判断这个数是否在第一个区间中，是的话对区间进行处理，不是的话则这个数列不是一个stack-sortable的数列。
对区间处理时，假设插入了x,区间为[l,r]，那么若\(x \neq l\ \&\ x \neq r\),就把区间分为[l,x-1]和[x+1,r]。否则直接更改区间为[l,r-1]或[l+1,r]即可。
最后生成整个数列时，只要将这些区间从前到后对于每个区间中的数从大到小输出即可。
代码
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
| #include <cstdio>
int a[200100];
struct Point
{
trueint l,r;
truePoint* next;
truePoint(int l=0,int r=0,Point* next=NULL):l(l),r(r),next(next) {}
};
struct S
{
trueint a[200100];
truePoint* b;
truebool Insert(int x)
{
truetrueif (x < b->l || x> b->r)
truetruetruereturn false;
truetrueif (x==b->l && x==b->r)
truetrue{
truetruetruePoint*p = b;
truetruetrueb = b-> next;
truetruetruedelete p;
truetrue}else if (x==b->r)
truetrue{
truetruetrueb->r = x-1;
truetrue}else if (x==b->l)
truetrue{
truetruetrueb->l = x+1;
truetrue}else{
truetruetruePoint* c = new Point(x+1,b->r,b->next);
truetruetrueb->r = x-1;
truetruetrueb->next = c;
truetrue}
truetruea[++a[0]] = x;
truetruereturn true;
true}
truevoid Make()
{
truetruewhile (b!=NULL)
truetrue{
truetruetruefor (int i = b->r; i>= b->l; i--)
truetruetruetruea[++a[0]] = i;
truetruetruePoint* p = b;
truetruetrueb = b->next;
truetruetruedelete p;
truetrue}
truetruereturn;
true}
}St;
int main()
{
trueint n,k;
truescanf("%d%d",&n,&k);
trueSt.b = new Point(1,n,NULL);
trueSt.a[0] = 0;
truefor (int i = 1; i<=k; i++)
true{
truetruescanf("%d",&a[i]);
truetrueif (!St.Insert(a[i]))
truetrue{
truetruetrueprintf("-1");
truetruetruereturn 0;
truetrue}
true}
trueSt.Make();
truefor (int i = 1; i<=St.a[0]; i++)
truetrueprintf("%d ",St.a[i]);
}
|