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 <wbr>2019(Cornfields):二维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;
}




相关文章
|
存储
|
算法 数据建模 机器学习/深度学习
|
测试技术
POJ 1001
此题用最朴素的思路实现即可,需模拟加法器,乘法器,最烦人的地方是特殊情形,如末位是小数点(12.^2=144,取小数点),整数末位是0(100^2=10000),0次幂,测试用例可能超出题目中说的范围,可能包含0次幂(100.0^0=0, 0.10^1=0.1)。
751 0
|
人工智能 BI
poj-3094-quicksum
http://poj.org/problem?id=3094 很简单 #include #include using namespace std; int main() { string a; int sum=0; while(getline(cin...
576 0
|
算法 机器人 编译器
POJ-2632
#include int main() { int k,a,b,n,m,i,j,num,rep,rect[100][100],robot[100][3]; int flag; char c; for(scanf("%d...
923 0