蒟蒻急求各位dalao帮助

P1440 求m区间内的最小值

WEUFSJI @ 2018-08-13 17:09:18

include<iostream>

include<cstdio>

include<cstring>

include<queue>

using namespace std; struct a{ int jz; int sj; }q[2000005]; int front=1; int tail=0; void push(int x,int i){ tail++; q[tail].jz=x; q[tail].sj=i; } void dscd(){ front++; } void dwcd(){ tail--; } int main(){ int n,m; scanf("%d %d",&n,&m); printf("0\n"); int x; for(int i=1;i<n;i++){ scanf("%d",&x); while( front <= tail && q[tail].jz>=x){ dwcd(); } push(x,i); while(q[front].sj<i-m+1){ dscd(); } printf("%d\n",q[front].jz); } return 0; }

                              代码如上

不写加粗部分会WA三个点写了就A了

蒟蒻急求各位dalao帮助

by Juanzhang @ 2018-08-13 17:12:34

include<iostream>
include<cstdio>
include<cstring>
include<queue>
using namespace std; struct a{ int jz; int sj; }q[2000005]; int front=1; int tail=0; void push(int x,int i){ tail++; q[tail].jz=x; q[tail].sj=i; } void dscd(){ front++; } void dwcd(){ tail--; } int main(){ int n,m; scanf("%d %d",&n,&m); printf("0\n"); int x; for(int i=1;i<n;i++){ scanf("%d",&x); while( front <= tail && q[tail].jz>=x){ dwcd(); } push(x,i); while(q[front].sj<i-m+1){ dscd(); } printf("%d\n",q[front].jz); } return 0; }

by agicy @ 2018-08-13 17:20:18

楼主的代码如下。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct a {
    int jz;
    int sj;
} q[2000005];
int front=1;
int tail=0;
void push(int x,int i) {
    tail++;
    q[tail].jz=x;
    q[tail].sj=i;
}
void dscd() {
    front++;
}
void dwcd() {
    tail--;
}
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    printf("0\n");
    int x;
    for(int i=1; i<n; i++) {
        scanf("%d",&x);
        while( front <= tail && q[tail].jz>=x) {
            dwcd();
        }
        push(x,i);
        while(q[front].sj<i-m+1) {
            dscd();
        }
        printf("%d\n",q[front].jz);
    }
    return 0;
}