Gravatar
jacken
积分:98
提交:23 / 34

Pro495  [POJ 2823]滑动窗口

可以用RMQ

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int a[N];
int f[N][20];
int n,k;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i][0] = a[i];
    }
    for(int i = 1;i<=log2(n);i++)
    {
        for(int j = 1;j<=n-(1<<i)+1;j++)
        {
            f[j][i] = min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
        }
    }
    for(int i = 1;i+k-1<=n;i++)
    {
        int x = i,y = i+k-1;
        int k = log2(y-x+1);
        printf("%d ",min(f[x][k],f[y-(1<<k)+1][k]));
    }
    printf("\n");
    for(int i = 1;i<=n;i++)
    {
        f[i][0] = a[i];
    }
    for(int i = 1;i<=log2(n);i++)
    {
        for(int j = 1;j<=n-(1<<i)+1;j++)
        {
            f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
        }
    }
    for(int i = 1;i+k-1<=n;i++)
    {
        int x = i,y = i+k-1;
        int k = log2(y-x+1);
        printf("%d ",max(f[x][k],f[y-(1<<k)+1][k]));
    }
    return 0;
}


2024-01-06 18:47:43    
我有话要说
暂无人分享评论!