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