#188-[RMQ]Balanced Lineup

Description

对于每天的挤奶，Farmer John的N头奶牛（1≤ N ≤50,000）总是以相同的顺序排队。有一天，农夫约翰决定与一些奶牛组织一场终极飞盘游戏。为了使事情变得简单，他将从奶牛阵容中接过一些的奶牛来玩游戏。然而，为了让所有的牛都玩得开心，它们的高度不应该有太大差异。农夫约翰已经量了所有奶牛的高度（1≤ 高度 ≤1,000,000）并把它们分为Q个（1≤ Q ≤200,000）奶牛组。对于每个组，他希望得到你的帮助来确定组中最矮和最高的牛之间的高度之差。 

Input

第一行：两个空间分开的整数，N和Q。 
线2 .. N+ 1行:包含一个单一的整数，第i头牛的高度
线N+2 …N + Q+ 1：两个整数A和B（1≤ A ≤ B ≤N），代表从A到B这个范围的牛。

Output

每行包含单个整数，表示每组内最高和最矮母牛之间的高度差。

1
2
3
4
5
6
7
8
9
10
6 3
1
7
3
4
2
5
1 5
4 6
2 2

• Sample Input

1
2
3
6
3
0

• Sample Output

• RMQ模板?

• 复制代码#include <iostream> #include <cmath> #define SIZE 50010 #define NUM 30 using namespace std; int maxdp[SIZE][NUM], mindp[SIZE][NUM]; // 最大值,最小值 int main(void) { int n, m, x, y, i, j, h; scanf("%d%d", &n, &m); for (i = 1; i <= n; ++i) { scanf("%d", &x); maxdp[i][0] = mindp[i][0] = x; } for (j = 1; (1 << j) <= n; ++j) // 开始位置 { for (i = 1; i + (1 << j) - 1 <= n; ++i) // 区间长度是2^j { maxdp[i][j] = max(maxdp[i][j-1], maxdp[i+(1<<(j-1))][j-1]); // 开始动归 mindp[i][j] = min(mindp[i][j-1], mindp[i+(1<<(j-1))][j-1]); } } while (m--) { scanf("%d%d", &x, &y); h = log(y - x + 1) / log(2); printf("%dn", max(maxdp[x][h], maxdp[y-(1<<h)+1][h]) - min(mindp[x][h], mindp[y-(1<<h)+1][h])); // 区间分成两段,查询 } return 0; }

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  #include <iostream>
  #include <cmath>
  
  #define SIZE 50010
  #define NUM 30
  
  using namespace std;
  
  int maxdp[SIZE][NUM], mindp[SIZE][NUM]; // 最大值,最小值
  
  int main(void)
  {
  	int n, m, x, y, i, j, h;
  	
  	scanf("%d%d", &n, &m);
  	for (i = 1; i <= n; ++i)
  	{
  		scanf("%d", &x);
  		maxdp[i][0] = mindp[i][0] = x;
  	}
  	for (j = 1; (1 << j) <= n; ++j) // 开始位置
  	{
  		for (i = 1; i + (1 << j) - 1 <= n; ++i) // 区间长度是2^j
  		{
  			maxdp[i][j] = max(maxdp[i][j-1], maxdp[i+(1<<(j-1))][j-1]); // 开始动归
  			mindp[i][j] = min(mindp[i][j-1], mindp[i+(1<<(j-1))][j-1]);
  		}
  	}
  	while (m--)
  	{
  		scanf("%d%d", &x, &y);
  		h = log(y - x + 1) / log(2);
  		printf("%dn", max(maxdp[x][h], maxdp[y-(1<<h)+1][h]) - min(mindp[x][h], mindp[y-(1<<h)+1][h])); // 区间分成两段,查询
  	}
  	
  	return 0;
  }

   

最后

以上就是负责小蘑菇最近收集整理的关于#188-[RMQ]Balanced Lineup的全部内容，更多相关#188-[RMQ]Balanced内容请搜索靠谱客的其他文章。