481
poj 2019 Cornfields【RMQ】
這道題是poj上一道還比較有名的二維RMQ (Range Minimum/Maximum Query 局部最大最小查詢)問題，但是可能是這道題的數據設計的不是很好，所以可以直接暴力過，先上暴力AC版本的代碼，之後會貼出RMQ正經版的代碼。。。
RMQ問題（區間詢問最值問題）。
題目大意：給出一個N*N矩形，每個格子上有一個價值。詢問一個b*b的矩形在左上角的位置(x,y)，(x+b-1,y+b-1)這一部分的最大值-最小值是多少。
題目分析：詢問次數很多，但是矩形隻有250且是正方形。二維的RMQ！
另外說一點，在poj評測時如果函數不返回值會編譯錯誤，一定要int返回型定義main函數。
#include<stdio.h>
#define MAXN 260
#define bigInt 100000
int bigLand[MAXN][MAXN]; //大塊土地
void work(int x,int y,int B)
{
//從坐標為(x,y)的地方開始
int i,j;
int max=-1;
int min=bigInt;
for (i=x;i<=x+B-1;i++)
{
for(j=y;j<=y+B-1;j++)
{
if (bigLand[i][j]>max)
max=bigLand[i][j];
if(bigLand[i][j]<min)
min=bigLand[i][j];
}
}
printf("%d\n",max-min);
}
int main()
{
//暴力解法
int N; //大塊土地邊長
int B; //指定的小塊土地邊長
int K; //查詢次數
int x,y; //每次查詢的坐標
int i,j;
while(scanf("%d%d%d",&N,&B,&K)!=EOF)
{
for (i=1;i<=N;i++)
for(j=1;j<=N;j++)
scanf("%d",&bigLand[i][j]);
for(i=0;i<K;i++)
{
scanf("%d%d",&x,&y);
work(x,y,B); //處理函數
}
}
return 0;
}
下麵是引用一位大牛的分析，講的很不錯
RMQ問題ST算法
ST算法O(nlogn)預處理,O(1)的查詢指定區間的最值(以最小值為例)
基本上是把待求區間[l,r]分為兩段長為len的區間
左邊一段為[l,l+len-1],右邊一段為[r-len+1,r]
len必須使得兩段區間覆蓋待求區間
設所求數組為w
那麼,所求最小值就是兩個區間的最小值間的最小值
即min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})
若都在預先處理中先求得兩個區間的最小值
則每次查詢的複雜度都是O(1)
---
對len做一個限製:隻能為2的冪
在預處理中求出所有mi[b][t] : 以b為起點,長為2^t的區間的最小值.
則求解min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})
就變成min(mi[l][t],mi[r-2^t+1][r]),其中t可以由此得出,以保證兩段區間可以覆蓋待求區間:
t=ln(r-l+1)/ln(2)
---
可以看到mi[b][t]=min(mi[b][t-1],mi[b+2^(t-1)-1][t-1])
特別地對於所有mi[i][0],其值都是w[i];
由此自底向上推出所有的mi[b][t]
mi大小為n*logn,預處理時間複雜度為O(nlogn),查詢時間複雜度為O(1)
個人觀點，RMQ問題的ST算法就是構建多顆二叉樹，隻不過多顆二叉樹沒有共同的根結點，隻有共同的葉子結點。。。
1<<n是把1 按2進製 左移n位，開始 1 的2進製表示是 0000 0001
1<<2是4,1<<3是8，所以1<<n相當於2^n
1<<16是65536
使用RMQ的AC代碼：
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define MAXN 260
using namespace std;
int bigLand[MAXN][MAXN]; //大塊土地
int pmax[MAXN][MAXN][11],pmin[MAXN][MAXN][11];
int max(int a,int b){ return a>b?a:b; }
int min(int a,int b){ return a<b?a:b; }
void init_rmq(int n)
{
int i;
for(i=1;i<=n;i++)
for(int j=1;j<=n;j++)
pmax[i][j][0]=pmin[i][j][0]=bigLand[i][j];
for(i=1;i<=n;i++)
for(int k=1;(1<<k)<=n;k++)
for(int j=1;j+(1<<k)-1<=n;j++)
{
pmax[i][j][k]=max(pmax[i][j][k-1],pmax[i][j+(1<<(k-1))][k-1]);
pmin[i][j][k]=min(pmin[i][j][k-1],pmin[i][j+(1<<(k-1))][k-1]);
}
}
void work(int x,int y,int B)
{
//從坐標為(x,y)的地方開始
int k=(int)(log(double(B))/log(2.0));
int maxans=-1; int minans=0x3f3f3f3f;
int l=y,r=y+B-1;
for(int i=x;i<x+B;i++)
{
maxans=max(maxans,max(pmax[i][l][k],pmax[i][r-(1<<k)+1][k]));
minans=min(minans,min(pmin[i][l][k],pmin[i][r-(1<<k)+1][k]));
}
printf("%d\n",maxans-minans);
}
int main()
{
//RMQ解法
int N; //大塊土地邊長
int B; //指定的小塊土地邊長
int K; //查詢次數
int x,y; //每次查詢的坐標
int i,j;
while(scanf("%d%d%d",&N,&B,&K)!=EOF)
{
for (i=1;i<=N;i++)
for(j=1;j<=N;j++)
scanf("%d",&bigLand[i][j]);
init_rmq(N);
for(i=0;i<K;i++)
{
scanf("%d%d",&x,&y);
work(x,y,B); //處理函數
}
}
return 0;
}
最後更新：2017-04-03 05:39:36