选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 。。。