数据改了 单调队列过不了 70分 3个点超时

P1440 求m区间内的最小值

ioio0614 @ 2018-03-31 20:27:42

include<iostream>

include<stdio.h>

using namespace std;

int a[2000002],q[2000002],p[2000002];

int main()

{

int n,m;

scanf("%d %d",&n,&m);

for(int i=1;i<=n;i++)
   scanf("%d",&a[i]);
cout<<"0"<<endl;
int head=1,tail=0;
for(int i=2;i<=n;i++)
{
    while(head<=tail&&q[tail]>a[i-1])
        tail--;
    q[++tail]=a[i-1];
    p[tail]=i-1;

    while(p[head]<i-m) head++;
     cout<<q[head]<<endl;
}
return 0;

}

by ioio0614 @ 2018-03-31 20:29:54

问一下啊滚动数组的优化 如果有大佬会的话

by AThousandSuns @ 2018-03-31 20:32:19

其实把cout改成printf就可能会过了……

by 小闸蟹 @ 2018-03-31 20:44:45

楼上正解

by ioio0614 @ 2018-04-03 21:21:40

@AThousandSuns 确实过了 但是为什么啊？？

by ioio0614 @ 2018-04-03 21:22:17


```#include<iostream>
#include<stdio.h>
using namespace std;
int a[2000002],q[2000002],p[2000002];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
       scanf("%d",&a[i]);
    cout<<"0"<<endl;
    int head=1,tail=0;
    for(int i=2;i<=n;i++)
    {
        while(head<=tail&&q[tail]>a[i-1])
            tail--;
        q[++tail]=a[i-1];
        p[tail]=i-1;

        while(p[head]<i-m) head++;
       //  cout<<q[head]<<endl;
         printf("%d\n",q[head]);
    }
    return 0;
}
```cpp

by panda_2134 @ 2018-04-26 08:12:43

std::cout不是一般的慢……

by zhuyunyu @ 2018-07-16 14:36:23

WQ，我也是这个问题。70分，三个超时过不了

by 啃丁狗 @ 2018-11-06 20:57:34

@zhuyunyu cout换成printf

|