?

poj 3264 Balanced Lineup@

2016-07-27 11:15?49人閱讀?評論(0)?收藏?舉報 ?分類： RMQ(Range MinimumMaximum Quer)（4）? Balanced Lineup

Time Limit:?5000MS	?	Memory Limit:?65536K
Total Submissions:?45854	?	Accepted:?21536
Case Time Limit:?2000MS

Description

For the daily milking, Farmer John's?N?cows (1 ≤?N?≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of?Q?(1 ≤?Q?≤ 200,000) potential groups of cows and their heights (1 ≤?height?≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers,?N?and?Q.?
Lines 2..N+1: Line?i+1 contains a single integer that is the height of cow?i?
Lines?N+2..N+Q+1: Two integers?A?and?B?(1 ≤?A?≤?B?≤?N), representing the range of cows from?A?to?B?inclusive.

Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

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

Sample Output

6 3

0

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int N = 50010; int ?minsum[N][20], maxsum[N][20], a[N]; void init(int n); void rmq(int n); int mmax(int l,int r); int mmin(int l,int r);int main() {int n, q;while(scanf("%d %d",&n, &q)!=EOF){for(int i=1;i<=n;i++){scanf("%d", &a[i]);}init(n);rmq(n);while(q--){int l, r;scanf("%d %d", &l, &r);if(l>r){swap(l,r);}int x=mmax(l,r);int y=mmin(l,r);printf("%d\n",x-y);}}return 0; }void init(int n) {for(int i=1;i<=n;i++){minsum[i][0]=a[i];maxsum[i][0]=a[i];}return ?; }void rmq(int n) {int k=int(log(n*1.0)/log(2.0));for(int j=1;j<=k;j++){for(int i=1;i<=n;i++){if(i+(1<<j)-1<=n){minsum[i][j]=min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);maxsum[i][j]=max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);}}} }int mmax(int l,int r) {int k=int(log((r-l+1)*1.0)/(log(2.0)));return max(maxsum[l][k],maxsum[r-(1<<k)+1][k]); }int mmin(int l,int r) {int k=int(log((r-l+1)*1.0)/(log(2.0)));return min(minsum[l][k],minsum[r-(1<<k)+1][k]); }

1. 概述

RMQ（Range Minimum/Maximum Query），即區(qū)間最值查詢，是指這樣一個問題：對于長度為n的數(shù)列A，回答若干詢問RMQ（A,i,j）(i,j<=n)，返回數(shù)列A中下標(biāo)在i，j之間的最小/大值。這兩個問題是在實際應(yīng)用中經(jīng)常遇到的問題，下面介紹一下解決這兩種問題的比較高效的算法。當(dāng)然，該問題也可以用線段樹（也叫區(qū)間樹）解決，算法復(fù)雜度為：O(N)~O(logN)，這里我們暫不介紹。

2.RMQ算法

對于該問題，最容易想到的解決方案是遍歷，復(fù)雜度是O(n)。但當(dāng)數(shù)據(jù)量非常大且查詢很頻繁時，該算法無法在有效的時間內(nèi)查詢出正解。

本節(jié)介紹了一種比較高效的在線算法（ST算法）解決這個問題。所謂在線算法，是指用戶每輸入一個查詢便馬上處理一個查詢。該算法一般用較長的時間做預(yù)處理，待信息充足以后便可以用較少的時間回答每個查詢。ST（Sparse Table）算法是一個非常有名的在線處理RMQ問題的算法，它可以在O(nlogn)時間內(nèi)進(jìn)行預(yù)處理，然后在O(1)時間內(nèi)回答每個查詢。

（一）首先是預(yù)處理，用動態(tài)規(guī)劃（DP）解決。

設(shè)A[i]是要求區(qū)間最值的數(shù)列，F[i, j]表示從第i個數(shù)起連續(xù)2^j個數(shù)中的最大值。（DP的狀態(tài)）

例如：

A數(shù)列為：3 2 4 5 6 8 1 2 9 7

F[1，0]表示第1個數(shù)起，長度為2^0=1的最大值，其實就是3這個數(shù)。同理 F[1,1] = max(3,2) = 3, F[1，2]=max(3,2,4,5) = 5，F[1，3] = max(3,2,4,5,6,8,1,2) = 8;

并且我們可以容易的看出F[i,0]就等于A[i]。（DP的初始值）

這樣，DP的狀態(tài)、初值都已經(jīng)有了，剩下的就是狀態(tài)轉(zhuǎn)移方程。

我們把F[i，j]平均分成兩段（因為f[i，j]一定是偶數(shù)個數(shù)字），從 i 到i + 2 ^ (j - 1) - 1為一段，i + 2 ^ (j - 1)到i + 2 ^ j - 1為一段(長度都為2 ^ (j - 1))。用上例說明，當(dāng)i=1，j=3時就是3,2,4,5 和 6,8,1,2這兩段。F[i，j]就是這兩段各自最大值中的最大值。于是我們得到了狀態(tài)轉(zhuǎn)移方程F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）。

代碼如下：

?

[cpp]?view plain?copy

void?RMQ(int?num)?//預(yù)處理->O(nlogn)??

{??

????for(int?j?=?1;?j?<?20;?++j)??

????????for(int?i?=?1;?i?<=?num;?++i)??

????????????if(i?+?(1?<<?j)?-?1?<=?num)??

????????????{??

????????????????maxsum[i][j]?=?max(maxsum[i][j?-?1],?maxsum[i?+?(1?<<?(j?-?1))][j?-?1]);??

????????????????minsum[i][j]?=?min(minsum[i][j?-?1],?minsum[i?+?(1?<<?(j?-?1))][j?-?1]);??

????????????}??

}??

這里我們需要注意的是循環(huán)的順序，我們發(fā)現(xiàn)外層是j，內(nèi)層所i，這是為什么呢？可以是i在外，j在內(nèi)嗎？

答案是不可以。因為我們需要理解這個狀態(tài)轉(zhuǎn)移方程的意義。

狀態(tài)轉(zhuǎn)移方程的含義是：先更新所有長度為F[i,0]即1個元素，然后通過2個1個元素的最值，獲得所有長度為F[i,1]即2個元素的最值，然后再通過2個2個元素的最值，獲得所有長度為F[i,2]即4個元素的最值，以此類推更新所有長度的最值。

而如果是i在外，j在內(nèi)的話，我們更新的順序就是F[1,0],F[1,1],F[1,2],F[1,3],表示更新從1開始1個元素，2個元素，4個元素，8個元素（A[0],A[1],....A[7]）的最值，這里F[1,3] = max(max(A[0],A[1],A[2],A[3]),max(A[4],A[5],A[6],A[7]))的值，但是我們根本沒有計算max(A[0],A[1],A[2],A[3])和max(A[4],A[5],A[6],A[7])，所以這樣的方法肯定是錯誤的。

為了避免這樣的錯誤，一定要好好理解這個狀態(tài)轉(zhuǎn)移方程所代表的含義。

（二）然后是查詢。

假如我們需要查詢的區(qū)間為(i,j)，那么我們需要找到覆蓋這個閉區(qū)間(左邊界取i，右邊界取j)的最小冪（可以重復(fù)，比如查詢5，6，7，8，9，我們可以查詢5678和6789）。

因為這個區(qū)間的長度為j - i + 1,所以我們可以取k=log2( j - i + 1)，則有：RMQ(A, i, j)=max{F[i , k], F[ j - 2 ^ k + 1, k]}。

舉例說明，要求區(qū)間[2，8]的最大值，k = log2（8 - 2 + 1）= 2，即求max(F[2, 2]，F[8 - 2 ^ 2 + 1, 2]) = max(F[2, 2]，F[5, 2])；

在這里我們也需要注意一個地方，就是<<運算符和+-運算符的優(yōu)先級。

比如這個表達(dá)式：5 - 1 << 2是多少？

答案是：4 * 2 * 2 = 16。所以我們要寫成5 - (1 << 2)才是5-1 * 2 * 2 = 1。

總結(jié)

以上是生活随笔為你收集整理的RMQ算法，求区间最值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。