Balanced Lineup POJ - 3264（RMQ）

4321 단어 데이터 구조
Balanced Lineup POJ - 3264
제목 연결
제목: 수열, Q 개의 질문, 구간 [A, B] 의 최대 값 과 최소 값 의 차 이 를 물 어 봅 니 다.사고방식: 라인 트 리 는 할 수 있 고 최대 최소 값 을 유지 할 수 있 으 며 직접 찾 으 면 됩 니 다.하지만 지금 은 RMQ 로 해 야 한다.RMQ 는 무엇 입 니까?(Range Minimum / Maximum Query) 구간 의 가장 값 을 묻 고 O (nlogn) 의 예비 처 리 를 통 해 O (1) 시간 내 에 구간 의 가장 값 을 찾 을 수 있 습 니 다.다음은 최대 치 를 예 로 들 면 fmax [i] [j] 로 구간 [i, i + 2 ^ j] 의 최대 치 를 표시 합 니 다.그러면 F [i] [j] = max (F [i] [j - 1], F [i + 2 ^ (j - 1)] [j - 1]);
init(){
    for(int j=1; (1<for(int i=1; i+(1<1<=n; i++){
            Fmax[i][j]=max(Fmax[i][j-1], Fmax[i+(1<1))][j-1]);
        }
    }
}

구간 [A, B] 내 문의:
int k=(int)(log(B-A+1.0)/log(2.0));
query(A, B)=max(Fmax[A][k], Fmax[B-(1<][k]);

이 문제 코드:
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=5e4+10;
int Fmax[maxn][20], Fmin[maxn][20], n, Q;
void init(){
    for(int i=1; (1<for(int j=1; j+(1<1<=n; j++){
            Fmax[j][i]=max(Fmax[j][i-1], Fmax[j+(1<1))][i-1]);
            Fmin[j][i]=min(Fmin[j][i-1], Fmin[j+(1<1))][i-1]);
        }
    }
}
int main(){
    while(~scanf("%d%d", &n, &Q)){
        for(int i=1; i<=n; i++){
            scanf("%d", &Fmax[i][0]);
            Fmin[i][0]=Fmax[i][0];
        }
        init();
        while(Q--){
            int x, y;
            scanf("%d%d", &x, &y);
            int k=(int)(log(y-x+1.0)/log(2.0));
            printf("%d
", max(Fmax[x][k], Fmax[y-(1<1][k])-min(Fmin[x][k], Fmin[y-(1<1][k]));
        }
    }   
    return 0;
}
데이터 구조 알고리즘 - 단일 체인 테이블 및 그 조작
Dapper는 스토리지 프로세스를 완벽하게 지원

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage