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

代码：

 1 #include<iostream>
 2 
 3 #include<cmath>
 4 
 5 #include<math.h>
 6 
 7 using namespace std;
 8 
 9 int ty(int a)//求2的a次方
10 
11 {
12 
13                int k=1;
14 
15                for(int i=0;i<a;i++) k*=2;
16 
17                return k;
18 
19 }
20 
21 int f[101][101],a[100100];
22 
23 /*   
24 
25 f[101][101]列表
26 
27 例如：数组a如下
28 
29 2 1 5 4 7
30 
31 1              2 1 5 4 7
32 
33 2              1 1 4 4 7
34 
35 3              1 1 4 4 7
36 
37 4              1 1 4 4 7
38 
39 5              1 1 4 4 7
40 
41 */
42 
43 int main()
44 
45 {
46 
47 int  i , j , k , n , x , y;
48 
49 cin>>n; //输入
50 
51 for(i=1;i<=n;i++)ci n>>a[i],f[0][i]=a[i];
52 
53                     cin>>x>>y;
54 
55 for(i=1;i<=y-x;i++)//求解
56 
57 {
58 
59                         for(j=1;j<=n;j++)
60 
61                         {//控制，如果“j+ty(i-1)>n”就超界了。
62 
63                               if(j+ty(i-1)>n)f[i][j]=min(f[i/2][j],f[i/2][j+i/2]);
64 
65                               else f[i][j]=min(f[i-1][j],f[i-1][j+ty(i-1)]);
66 
67                               //cout<<f[i][j]<<" ";
68 
69                            }
70 
71                            //cout<<endl;
72 
73                    }
74 
75                    cout<<f[y-x][x];//输出
76 
77                system(“pause”);
78 
79 }

View Code

代码分析：

例如：数组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中最小的元素的值。