RMQ（非log2储存方法）

2016-03-31

RMQ

难度级别：B；运行时间限制：1000ms；运行空间限制：256000KB；代码长度限制：2000000B

试题描述

长度为n的数列A，以及q个询问，每次询问一段区间的最小值。

输入

第一行，一个整数n
第二行，n个数，表示A数组，用空格隔开。
第三行，一个正整数q
第4到第q+3行每行两个正整数L、R（L<=R），表示一段区间，用一个空格隔开。

输出

针对每个询问，输出结果。每个结果占一行。

输入示例

5
3 2 4 3 5
3
1 3
2 5
3 4

输出示例

2
2
3

其他说明

数据规模：n, q, Ai<=100000

代码：

 #include<iostream>

 #include<cmath>

 #include<math.h>

 using namespace std;

 int ty(int a)//求2的a次方

 {

                int k=;

                for(int i=;i<a;i++) k*=;

                return k;

 }

 int f[][],a[];

 /*

 f[101][101]列表

 例如：数组a如下

 2 1 5 4 7

 1              2 1 5 4 7

 2              1 1 4 4 7

 3              1 1 4 4 7

 4              1 1 4 4 7

 5              1 1 4 4 7

 */

 int main()

 {

 int  i , j , k , n , x , y;

 cin>>n; //输入

 for(i=;i<=n;i++)ci n>>a[i],f[][i]=a[i];

                     cin>>x>>y;

 for(i=;i<=y-x;i++)//求解

 {

                         for(j=;j<=n;j++)

                         {//控制，如果“j+ty(i-1)>n”就超界了。

                               if(j+ty(i-)>n)f[i][j]=min(f[i/][j],f[i/][j+i/]);

                               else f[i][j]=min(f[i-][j],f[i-][j+ty(i-)]);

                               //cout<<f[i][j]<<" ";

                            }

                            //cout<<endl;

                    }

                    cout<<f[y-x][x];//输出

                system(“pause”);

 }

代码分析：

例如：数组a[]={2 1 5 4 7};

因此可以列表如下：

1. 2(从第1个元素长度为1区间的最小值)

2. 1(从第2个元素长度为1区间的最小值)

3. 5(从第3个元素长度为1区间的最小值)

4. 4(从第4个元素长度为1区间的最小值)

5. 7(从第5个元素长度为1区间的最小值)；

1. 1(从第1个元素长度为2区间的最小值)

2. 1(从第2个元素长度为2区间的最小值)

3. 4(从第3个元素长度为2区间的最小值)

4. 4(从第4个元素长度为2区间的最小值)

5. 7(从第5个元素长度为2区间的最小值)

1. 1(从第1个元素长度为3区间的最小值)

2. 1(从第2个元素长度为3区间的最小值)

3. 4(从第3个元素长度为3区间的最小值)

4. 4(从第4个元素长度为3区间的最小值)

5. 7(从第5个元素长度为3区间的最小值)

可以得出公式: min(f[i-1][j],f[i-1][j+ty(i-1)]);

但如果这个公式超界了得出的结果可以为0，有些数据就会结果错误。所以，要加一个判断，如果j+ty(i-1)>n就要利用f[i][j]=min(f[i/2][j],f[i/2][j+i/2]);来求f[i][j]的结果。最后要输出f[y-x][x]，

代表从数组的下标为x的元素y-x中最小的元素的值。

Ty

RMQ（非log2储存方法）