luoguP1886 슬라이딩 창(단일 대기열 템플릿 문제)

3904 단어
제목 링크:https://www.luogu.org/problem/P1886#submit
제목: n 개의 수를 정하고, 크기가 k인 슬라이딩 창의 최소값과 최대값을 구하십시오.
사고방식: 단조로운 대기열 템플릿 문제.
AC 코드:
#include
#include
using namespace std;

const int maxn=1e6+5;
int n,k,head,tail;
int a[maxn],q[maxn],p[maxn];

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

 
전재 대상:https://www.cnblogs.com/FrankChen831X/p/11268652.html

좋은 웹페이지 즐겨찾기