범위 최소 / 최대 쿼 리 (RMQ) - 스 파스 테이블 알고리즘
코드 는 다음 과 같 습 니 다:
/*
* =====================================================================================
*
* Filename: RMQ_st.CPP
*
* Description: Range Min/Max Query - st algorithm
*
* Version: 1.0
* Created: 07/13/11 13:33:45
* Revision: none
* Compiler: gcc
*
* Author: nomad2
*
* =====================================================================================
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 200001;
int a[N], d[20];
int st[N][20];
void readIn(int n)
{
int i;
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
}
void initRMQ(int n)
{
int i, j;
for(d[0] = 1, i = 1; i < 21; i++)
{
d[i] = 2 * d[i-1];
}
for(i = 0; i < n; i++)
{
st[i][0] = a[i];
}
int k = int(log(double(n))/log(2)) + 1;
for(j = 1; j < k; j++)
{
for(int i = 0; i < n; i++)
{
if(i + d[j-1] - 1 < n)
{
st[i][j] = max(st[i][j-1], st[i + d[j-1]][j-1]);
}
else
{
break; // st[i][j] = st[i][j-1];
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < k; j++)
{
printf("%d ", st[i][j]);
}
printf("
");
}
}
void query(int Q)
{
int i;
for(i = 0; i < Q; i++)
{
int x, y, k;
scanf("%d%d", &x, &y);
k = int(log(double(y-x+1))/log(2.0));
printf("%d
", max(st[x][k], st[y - d[k]+1][k]));
}
}
int main()
{
int n, Q;
while(scanf("%d%d", &n, &Q) != EOF)
{
readIn(n);
initRMQ(n);
query(Q);
}
return 0;
}
테스트 결과:
[pa004306: ]
>> cat input1
8 3
4 5 7 2 1 3 6 9
1 2
2 4
3 7
[pa004306: ]
>> cat input1 |./a.exe
4 5 7
5 7 7
7 7 7
2 2 6
1 3 9
3 6 9
6 9 9
9 9 0
7
7
9
연습 은 POJ 3264 를 참고 할 수 있 습 니 다.
여 기 는 다른 버 전 입 니 다. ST 시 계 는 가로로 되 어 있 고 위 에는 세로 로 되 어 있 습 니 다.
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100;
int st[20][N], ln[N], val[N];
int n = 9;
void initrmq(int n)
{
int i, j, k, sk;
ln[0] = ln[1] = 0;
for(i = 0; i < n; i++)
{
st[0][i] = val[i];
}
for(i = 1, k = 2; k < n; i++, k <<= 1)
{
printf("k is %d
", k);
for(j = 0, sk = (k>>1); j < n; j++, sk++)
{
st[i][j] = st[i-1][j];
if(sk < n && st[i][j] > st[i-1][sk])
{
st[i][j] = st[i-1][sk];
}
}
ln[0] = -1;
for(j = (k>>1); j < k; j++)
{
ln[j] = ln[(k>>1)-1] + 1;
}
}
ln[0] = 0;
/*
for(j = (k>>1) + 1; j <= k; j++)
{
ln[j] = ln[k>>1] + 1;
} */
}
void print()
{
for(int i = 0; i < 5; i++)
{
for(int j = 0; j < n; j++)
{
printf("%d ", st[i][j]);
}
printf("
");
}
printf("ln is ");
for(int i = 0; i < n; i++)
{
printf("%d ", ln[i]);
}
printf("
");
}
// min of (val[x]...val[y])
int query(int x, int y)
{
int bl = ln[y-x+1];
return min(st[bl][x], st[bl][y-(1<<bl)+1]);
}
int main()
{
int v[] = {9, 5, 6, 7, 8, 3, 4, 2, 1};
n = sizeof(v)/sizeof(int);
for(int i = 0; i < n; i++)
{
val[i] = v[i];
}
initrmq(n);
print();
for(int x = 0; x < n; x++)
{
//for(int y = x; y < n; y++)
int y = x + 1;
{
printf("min between %d and %d is %d
", x, y, query(x, y));
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.