POJ 2823 슬라이딩 윈도(RMQ + 스크롤 배열)

2049 단어
정상적인 RMQ 질문 구간의 최대 최소값 문제는 일반적인 dp[i][j]를 켜면 메모리를 초과할 수 있습니다.
제목에서 질문의 구간 길이 k를 정했기 때문에 한 개의 그룹으로 dp[i]를 저장하여 i+k-1 구간의 최값을 표시하십시오
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//  INT_MAX   
#define MAX 1000050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///      
using namespace std;
int dp1[MAX],dp2[MAX],a[MAX]; // dp[i]  i i+k-1     
int n,m,k;
inline int min(int a,int b) {
    return a < b ? a : b;
}
inline int max(int a,int b) {
    return a < b ? b : a;
}
void initRMQ() {
    for(int i=1; i<=n; i++) {
        dp1[i] = a[i];
        dp2[i] = a[i];
    }
    for(int j=1; j<=k; j++) {
        for(int i=1; i<=n; i++) {
            if(i + (1 << (j-1)) <= n) {
                dp1[i] = min(dp1[i],dp1[i + (1 << (j-1))]);
                dp2[i] = max(dp2[i],dp2[i + (1 << (j-1))]);
            }
        }
    }
}

int askRMQ(int s,int e,int kind) {
    if(kind == 1) {
        return min(dp1[s],dp1[e - (1 << k) + 1]);
    } else return max(dp2[s],dp2[e - (1 << k) + 1]);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    k = log(double(m)) / log(double(2));
    initRMQ();
    printf("%d",askRMQ(1,m,1));
    for(int i=2; i<=n-m+1; i++) {
        printf(" %d", askRMQ(i,i+m-1,1));
    }
    puts("");
    printf("%d",askRMQ(1,m,2));
    for(int i=2; i<=n-m+1; i++) {
        printf(" %d",askRMQ(i,i+m-1,2));
    }
    puts("");
    return 0;
}

좋은 웹페이지 즐겨찾기