題目描述

每天,農夫 John 的N(1 <= N <= 50,000)頭牛總是按同一序列排隊. 有一天, John 決定讓一些牛們玩一場飛盤比賽. 他準備找一群在對列中為置連續的牛來進行比賽. 但是為了避免水平懸殊,牛的身高不應該相差太大. John 準備了Q (1 <= Q <= 200,000) 個可能的牛的選擇和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一組里面最高和最低的牛的身高差別.

輸入輸出格式

輸入格式：

第1行：N,Q

第2到N+1行：每頭牛的身高

第N+2到N+Q+1行：兩個整數A和B，表示從A到B的所有牛。（1<=A<=B<=N）

輸出格式：

輸出每行一個數，為最大數與最小數的差

輸入輸出樣例

輸入樣例#1：

6 3
1
7
3
4
2
5
1 5
4 6
2 2

輸出樣例#1：
6
3
0

思路：一道 RMQ 模版題，每次詢問區間 [a,b] 的極差，預處理最大值與最小值的 ST 表后，相減即為答案

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int>const int MOD = 1E9+7; const int N = 1000000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;int dpMax[N][20]; int dpMin[N][20]; int a[N]; void initMax(int n){//初始化最大值查詢for(int i=1;i<=n;i++)dpMax[i][0]=a[i];for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)dpMax[i][j]=max(dpMax[i][j-1],dpMax[i+(1<<(j-1))][j-1]); } int getMax(int L,int R){//查詢最大值//int k = (int)(log10(R-L+1)/log10(2));int k=0;while((1<<(k+1))<=R-L+1)k++;return max(dpMax[L][k],dpMax[R-(1<<k)+1][k]); }void initMin(int n){//初始化最小值查詢for(int i=1;i<=n;i++)dpMin[i][0]=a[i];for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)dpMin[i][j]=min(dpMin[i][j-1],dpMin[i+(1<<(j-1))][j-1]); } int getMin(int L,int R){//查詢最小值//int k = (int)(log10(R-L+1)/log10(2));int k=0;while((1<<(k+1))<=R-L+1)k++;return min(dpMin[L][k],dpMin[R-(1<<k)+1][k]); } int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);initMax(n);initMin(n);for(int i=1;i<=m;i++){int left,right;scanf("%d%d",&left,&right);int maxx=getMax(left,right);int minn=getMin(left,right);printf("%d\n",maxx-minn);}return 0; }

?

總結

以上是生活随笔為你收集整理的平衡的阵容（洛谷-P2880）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。