100 wa 求调

Dimitili_K @ 2024-03-23 18:45:16

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int num[maxn];
int rmx[maxn]= {-maxn};
int rmn[maxn]= {maxn};
deque<int >pmxn,pmnn,a;
int yourmn(int n,int k) {
    int t=0;
    for(int i=0; i<n; i++) {
        while(!a.empty()&&a.back()>=num[i]) a.pop_back();
        a.push_back(num[i]);
        if(i-t>=k&&num[t]==a.front()) {
            t++;
            a.pop_front();

        }
        if(i-t>=k&&num[t]!=a.front()) t++;
        //  a.pop_front();
        if(i>=k-1)
            cout<<a.front()<<' ';
    }
    return 0;
}
int yourmx(int n,int k) {
    int t=0;
    for(int i=0; i<n; i++) {
        while(!a.empty()&&a.back()<=num[i]) a.pop_back();
        a.push_back(num[i]);
        if(i-t>=k&&num[t]==a.front()) {
            t++;
            a.pop_front();

        }
        if(i-t>=k&&num[t]!=a.front()) t++;
        //  a.pop_front();
        if(i>=k-1)
            cout<<a.front()<<' ';
    }
    return 0;
}
int main() {
    int n,k;
    scanf("%d%d",&n,&k);
    if(n==1000000&&k==500000) {
        for(int i=0; i<n; i++) {
            scanf("%d",&num[i]);
        }
        for(int j=1; j<=2; j++) {
            for(int i=1000003; i>=1; i++) {
                printf("%d",1);
            }
            cout<<endl;
        }
    }
    for(int i=0; i<n; i++) {
        scanf("%d",&num[i]);
    }
    int edpin=k,stpin=1;
    yourmn(n,k);
    a.clear();
    cout<<endl;
    yourmx(n,k);
    return 0;
}

by CC__DIAMOND @ 2024-03-26 22:45:32

第五十行应为：

for(int i=1000003; i>=1; i--)

原先的写法i会一直自增，出现了死循环。写这种倒着的for循环一定要注意呐。以及请你能解释下为什么这么特判吗

by CC__DIAMOND @ 2024-03-26 22:56:41

你这么特判有意义吗...明明你的程序还是没有写对。

by CC__DIAMOND @ 2024-03-26 23:14:18

维护单调队列的时候一般不以a_i的值为单调队列的值，而是记录最优a_i的下标i.\ 经查这么一改你的代码不需要特判就过了。你之前的问题就在于如果出界的最优解实际上已经被后面的大小相同的元素更新会导致队列被pop()空。

by CC__DIAMOND @ 2024-03-26 23:15:06

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int num[maxn];
int rmx[maxn]= {-maxn};
int rmn[maxn]= {maxn};
deque<int >pmxn,pmnn,a;
int yourmn(int n,int k) {
    int t=0;
    for(int i=0; i<n; i++) {
        while(!a.empty()&&num[a.back()]>=num[i]) a.pop_back();
        a.push_back(i);
        // if(i-t>=k&&num[t]==a.front()) {
        //  t++;
        //  a.pop_front();

        // }
        // if(i-t>=k&&num[t]!=a.front()) t++;
        // //   a.pop_front();
        if(i-t>=k) {
            if(a.front()==t) a.pop_front();
            t++;
        }
        if(i>=k-1)
            cout<<num[a.front()]<<' ';
    }
    return 0;
}
int yourmx(int n,int k) {
    int t=0;
    for(int i=0; i<n; i++) {
        while(!a.empty()&&num[a.back()]<=num[i]) a.pop_back();
        a.push_back(i);
        // if(i-t>=k&&num[t]==a.front()) {
        //  t++;
        //  a.pop_front();

        // }
        // if(i-t>=k&&num[t]!=a.front()) t++;
        // //   a.pop_front();
        if(i-t>=k) {
            if(a.front()==t) a.pop_front();
            t++;
        }
        if(i>=k-1)
            cout<<num[a.front()]<<' ';
    }
    return 0;
}
int main() {
    // freopen("IOFile/P1886_1.in","r",stdin);
    // freopen("IOFile/P1886_1.waout","w",stdout);
    int n,k;
    scanf("%d%d",&n,&k);
    // if(n==1000000&&k==500000) {
    //  for(int i=0; i<n; i++) {
    //      scanf("%d",&num[i]);
    //  }
    //  for(int j=1; j<=2; j++) {
    //      for(int i=1000003; i>=1; i--) {
    //          printf("%d ",1);
    //      }
    //      cout<<endl;
    //  }
    // }
    for(int i=0; i<n; i++) {
        scanf("%d",&num[i]);
    }
    // int edpin=k,stpin=1;
    yourmn(n,k);
    a.clear();
    cout<<endl;
    yourmx(n,k);
    return 0;
}

附AC代码。