POJ 2823 슬라이딩 윈도(RMQ + 스크롤 배열)
제목에서 질문의 구간 길이 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.