—— Summon, Light!
0%

POJ 2823 //单调队列

发表于 更新于 Valine：

选C++交
选C++交
选C++交
【重说三
因为是队里的专题训练。。。
所以我知道这题肯定是单调队列。。。
而且一看数据范围和时限。。。
12000ms 逗我？
随手一交。RE了。。。
再随手一交。尼玛！T了！！！
这怎么可能！！！
单调队列是 O(n) 啊！啊啊啊啊啊！！
然后再各种查资料查程序。。。
提交别人写的 AC 程序竟然还是TLE。。。
过了好几天（没错 好几天！）
跑到POJ的原题交了一下。
果然还是TLE了。。。
然后又开始搜各种搜。。。
直到发现这两个：
http://blog.csdn.net/chl_3205/article/details/8706307
http://blog.csdn.net/yihuikang/article/details/7771170
语言选到C++。。。果然 AC 了。。。
生无可恋的眼神 T^T

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
#include <cstdio>
#include <cstring>

const int N=1000010;
int a[N],q[N],c[N];

int  main()
{
	int n,k,i,l,r;
	scanf("%d%d",&n,&k);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	l=1;
	r=0;
	for (i=1;i<=k;i++)
	{
		while (q[r]>=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
	}
	for (;i<=n;i++)
	{
		printf("%d ",q[l]);
		while (q[r]>=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
		if (i-k>=c[l]) l++;
	}
	printf("%d\n",q[l]);
	l=1;
	r=0;
	for (i=1;i<=k;i++)
	{
		while (q[r]<=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
	}
	for (;i<=n;i++)
	{
		printf("%d ",q[l]);
		while (q[r]<=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
		if (i-k>=c[l]) l++;
	}
	printf("%d\n",q[l]);
	return 0;
}

这个实在是太诡异了。。。
一般情况下我都是认为 G++ 比 VC++ 靠谱的
【当然 MinGW 算是其中比较不靠谱的。。。
而且编译环节还都没有问题。。。

===============当天的更新===============
有学长告诉我这个是 IO 的问题 加了读入输出优化就可以过
然后我又去写了一下

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
#include <cstdio>
#include <cstring>

const int N=1000010;
int a[N],q[N],c[N];

void read(int &x)
{
	char c=getchar();
	x=0;
	while (!(c>='0'&&c<='9'||c=='-')) c=getchar();
	int f=0;
	if (c=='-')
	{
		f=1;
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();	
	}
	if (f) x=-x;
}

void write(int x)
{
	if (x==0)
	{
		putchar('0');
		return;
	}
	if (x<0) putchar('-'),x=-x;
	char s[20];
	int i=0;
	while (x)
	{
		s[i++]=x%10+'0';
		x/=10;
	}
	s[i]=0;
	for (i--;i>=0;i--) putchar(s[i]);
}

int  main()
{
	int n,k,i,l,r;
	read(n);
	read(k);
	for (i=1;i<=n;i++) read(a[i]);
	l=1;
	r=0;
	for (i=1;i<=k;i++)
	{
		while (q[r]>=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
	}
	for (;i<=n;i++)
	{
		write(q[l]);
		putchar(' ');
		while (q[r]>=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
		if (i-k>=c[l]) l++;
	}
	write(q[l]);
	puts("");
	l=1;
	r=0;
	for (i=1;i<=k;i++)
	{
		while (q[r]<=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
	}
	for (;i<=n;i++)
	{
		write(q[l]);
		putchar(' ');
		while (q[r]<=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
		if (i-k>=c[l]) l++;
	}
	write(q[l]);
	puts("");
	return 0;
}

果然 AC 了。
这个倒是比较符合我对 G++ 的印象
一般 -o 是不会有什么优化的
那这个问题就比较无聊了。。。
真正用的时候肯定不是 -o 。。。

咖啡，亦我所需也