亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

區(qū)間第K大值與RMQ問題

系統(tǒng) 2033 0

?? ? ?這次我們討論一下有關(guān)區(qū)間中的值的問題。如果你只想看RMQ,請?zhí)^下面這幾段,在第一段代碼的后面有詳細(xì)的講解。

?? ? ?在競賽中,我們經(jīng)常遇到最值問題。但是出題者往往給我們出一些這樣的題目,讓我們找到第K優(yōu)解,而不是最優(yōu),比如K小生成樹、K優(yōu)背包等等。這篇文章主要介紹另一個(gè)“K問題“,區(qū)間第K大值。

?? ? ?區(qū)間第K大值的題意很明確,對(duì)于一個(gè)區(qū)間,找到其中第K大的一個(gè)數(shù)輸出。這個(gè)問題可以用O(n 2 )的算法枚舉,但是當(dāng)區(qū)間很大的時(shí)候這種方法就會(huì)很費(fèi)時(shí)。我們還可以將區(qū)間內(nèi)的序列排序,直接輸出a[k+l-1](l是區(qū)間左端點(diǎn))即可。

?? ? ?我們知道,快排的原理是找到一個(gè)標(biāo)準(zhǔn)點(diǎn),然后進(jìn)行交換、分組,直到它的左邊(以遞增為例)都比它小,右邊都比它大為止。但是結(jié)合這道題來說,每進(jìn)行一遍分 ? ? ?組,第K大值就會(huì)確定的位于其中一組,或者就是那個(gè)標(biāo)準(zhǔn)點(diǎn)。然后我們只用將有第K大值的那個(gè)組再進(jìn)行分組、查找(不是標(biāo)準(zhǔn)點(diǎn)),或者直接輸出標(biāo)準(zhǔn)點(diǎn)(正好是標(biāo)準(zhǔn)點(diǎn))。這樣,我們就可以以少于1/2的操作找到我們想要的數(shù)。

?? ? ?對(duì)于多次詢問,我們要保留下原始序列,以免之后再尋找時(shí)出現(xiàn)錯(cuò)誤。

?? ? ?給出一道比較水的題,大家可以試一下~

?

?

      
【題目描述】(rqnoj350)
給出一個(gè)長度為N的序列A1,A2,A3,...,AN,其中每項(xiàng)都是
小于10
^ 5的自然數(shù)。
現(xiàn)在有M個(gè)詢問,每個(gè)詢問都是Ai...Aj中第k小的數(shù)等
于多少。
數(shù)據(jù)范圍:
在60
% 的數(shù)據(jù)中, 1 ≤N≤ 1000 1 ≤M≤ 1000
在100
% 的數(shù)據(jù)中, 1 ≤N≤ 10000 , 1 ≤M≤ 2000

【輸入格式】
第一行兩個(gè)正整數(shù)N,M。
第二行N個(gè)數(shù),表示序列A1,A2,...,AN。
緊著的M行,每行三個(gè)正整數(shù)i,j,k(k≤j
- i + 1 ),表示
詢問Ai...Aj中第k小的數(shù)等于多少。

【輸出格式】
共輸出M行,第i行輸出第i個(gè)詢問的答案。

【樣例輸入】
4 3
4 1 2 3
1 3 1
2 4 3
1 4 4

【樣例輸出】
1
3
4

?

?

?

?? ? ?分析就不用了,直接貼代碼吧~

?

?? ? ?參考代碼:

?

      
1 program knum;
2 var
3 a,t: array [ 1 .. 3000000 ] of longint;
4 n,k,i,m,l,r:longint;
5 function sort(l,r,k:longint):longint; // 改編的快排
6 var
7 i,j,x,y:longint;
8 begin
9 if l = r then exit(a[l]); // 兩指針可能重合。這條語句可以減少時(shí)間消耗
10 i: = l;
11 j: = r;
12 x: = a[(i + j) shr 1 ];
13 repeat
14 while a[i] < x do inc(i);
15 while a[j] > x do dec(j);
16 if i <= j then
17 begin
18 y: = a[i];
19 a[i]: = a[j];
20 a[j]: = y;
21 inc(i);
22 dec(j);
23 end ;
24 until i > j;
25 if (k >= i) then exit(sort(i,r,k)); //
26 if (k <= j) then exit(sort(l,j,k));
27 exit(x); // 如果是標(biāo)準(zhǔn)點(diǎn)就直接輸出
28 end ;
29 begin
30 readln(n,m);
31 for i: = 1 to n do
32 read(t[i]);
33 for i: = 1 to m do
34 begin
35 a: = t; // 保留原序列,對(duì)“鏡子“序列進(jìn)行操作
36 readln(l,r,k);
37 writeln(sort(l,r,l + k - 1 )); //
38 end
39 end .
40 P.S.① a)因?yàn)閗∈[l,r],所以不用判斷i是否小于r;
41 b)由于i > j,這條語句和以下兩條語句沒有交集。
42 ②一定是l + k - 1 ,因?yàn)槭菂^(qū)間的第K小值,所以尋找k肯定不對(duì)。
?

?

?

?

?? ? ?當(dāng)然,對(duì)于區(qū)間最值問題(RMQ),這種方法也能解決。為什么還要有求區(qū)間最值(RMQ)的偉大的ST算法呢?

?? ? ?有句頗有哲理的話說得好,存在即合理。師傅告訴我,上面改裝快排的時(shí)間效率是O(nm),所以當(dāng)m很大時(shí),這種方法就無法快速出解了。這時(shí),強(qiáng)大的ST(Sparse Table)算法應(yīng)運(yùn)而生(為了劇情需要^_^)!ST算法可以在O(nlogn)的時(shí)間中構(gòu)造一個(gè)強(qiáng)大的數(shù)組,然后只用O(1)的時(shí)間就能針對(duì)每次詢問找到解。

?? ? ?這個(gè)強(qiáng)大的數(shù)組的名字叫做f[i,j](好俗…),表示從區(qū)間的第i位開始,長度為2 i 的區(qū)間的最大值(姑且以求區(qū)間最大值為例)。這句話聽起來很玄乎,可是怎么構(gòu)造這個(gè)數(shù)組呢?

?? ? ?我們先把f[i,0]賦成讀入的第i個(gè)數(shù)(也就是以i為起點(diǎn),長度為2 0 =1的區(qū)間內(nèi)的最值)。因?yàn)閖表示長度為2 j ,所以我們可以把整個(gè)f[i,j]表示的區(qū)間劃分[i,j-1]和[i+2 (j-1) ,j-1]兩個(gè)區(qū)間,然后調(diào)用f中存儲(chǔ)的兩個(gè)區(qū)間中的最大值,取其中較大的那個(gè)就行!

?? ? ?有的人可能疑惑,f[i,j]劃分的兩個(gè)空間的最值是什么時(shí)候求出來的呢?別忘了我們的初始化。有了j=0時(shí)的最值,j=1時(shí)的最值就很好求了。顯然,j的最大值是trunc(log 2 n),這樣,我們只要讓j從1循環(huán)到trunc(log 2 n),把目的區(qū)間由小逐漸擴(kuò)大,之后就能隨意地調(diào)用原來的解啦!整個(gè)過程循環(huán)完以后,任何一個(gè)長度為2 j 的區(qū)間的最值就全部求出來了。

?? ? ?長度為2 j 區(qū)間的最值是有了,但是如果詢問的區(qū)間的長度2 j 和2 j+1 之間呢?舉一個(gè)例子。假設(shè)原序列是4 2 8 6 1 7 3,求3到7這個(gè)區(qū)間的最大值。

區(qū)間第K大值與RMQ問題

?? ? ?尋找的時(shí)候就只用尋找圖中的兩個(gè)區(qū)間的最大值即可,這樣整個(gè)區(qū)間就都能夠被覆蓋,即使交集也不會(huì)影響結(jié)果。

?? ? ?另外一道比較水的題,大家也可以試試~

?

      
【題目描述】(tyvj p1038)
老管家是一個(gè)聰明能干的人。他為財(cái)主工作了整整10年,財(cái)主為了讓自已賬目更加清楚。要求管家每天
記k次賬, 管家聰明能干,因而管家總是讓財(cái)主十分滿意。但是由于一些人的挑撥,財(cái)主還是對(duì)管家產(chǎn)生
了懷疑。于是他決定 種特別的方法來判斷管家的忠誠,他把每次的賬目按1, 2 3 …編號(hào),然后不定時(shí)的
問管家問題,問題是這樣的:在 a b號(hào)賬中最少的一筆是多少?為了讓管家沒時(shí)間作假他總是一次問多個(gè)問題。

【輸入格式】
輸入中第一行有兩個(gè)數(shù)m,n表示有m(m
<= 100000 )筆賬,n表示有n個(gè)問題,n <= 100000
第二行為m個(gè)數(shù),分別是賬目的錢數(shù)
后面n行分別是n個(gè)問題,每行有2個(gè)數(shù)字說明開始結(jié)束的賬目編號(hào)。

【輸出格式】
輸出文件中為每個(gè)問題的答案。具體查看樣例。

【樣例輸入】
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10

【樣例輸出】
2 3 1

?

?

?? ? ?參考代碼:

?

      
1 program ST;
2 var
3 f: array [ 0 .. 100000 , 0 .. 19 ] of longint; // j的最大值是trunc(log2n),計(jì)算器算一下
4 i,j,n,m,l,r:longint;
5 function min(x,y:longint):longint;
6 begin
7 if x < y then exit(x)
8 else exit(y);
9 end ;
10 begin
11 readln(n,m);
12 for i: = 1 to n do // 初始化f數(shù)組
13 read(f[i, 0 ]);
14 for j: = 1 to trunc(ln(n) / ln( 2 )) do // 循環(huán)j的長度
15 for i: = 1 to n - 1 << j + 1 do // i的最大值n - 1 << j + 1
16 f[i,j]: = min(f[i,j - 1 ],f[i + 1 << (j - 1 ),j - 1 ]); // 動(dòng)態(tài)規(guī)劃更新f數(shù)組,注意兩個(gè)區(qū)間
17 for i: = 1 to m do
18 begin
19 readln(l,r);
20 j: = trunc(ln(r - l + 1 ) / ln( 2 )); // j就是圖示中的k
21 write(min(f[l,j],f[r - 1 << j + 1 ,j]), ' ' ); // 跟圖中一樣
22 end ;
23 end .

?

?

?? ? ?終于寫完了~累死了…有什么不對(duì)的地方和說得不明白的地方歡迎大家提出!我一定盡快改正!

(Saltless原創(chuàng),轉(zhuǎn)載請注明出處)

?

區(qū)間第K大值與RMQ問題


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 国产精品区牛牛影院 | 一级一级18女人毛片 | 日本a视频在线观看 | 国产欧美在线不卡 | 四虎永久免费影院 | 午夜色网站 | 一区二区三区免费精品视频 | 国产免费午夜a无码v视频 | 免费成人小视频 | 亚洲视频中文字幕 | 毛片大全在线 | 久久久久久亚洲精品中文字幕 | 国产精品久久久久久久伊一 | 2018天天操 | 午夜福免费福利在线观看 | 台湾一级毛片永久免费 | 中文国产日韩欧美视频 | 欧美亚洲日本国产综合网 | 成人欧美精品一区二区不卡 | 四虎影院在线观看免费 | 久久99国产精品久久99无号码 | 久久久综合网 | 国产精品毛片久久久久久久 | 久青草国产在线 | 婷婷五月天.com | 激性欧美激情在线播放16页 | 99精品热线在线观看免费视频 | 日韩国产欧美成人一区二区影院 | 激情综合色综合久久综合 | 亚洲欧美一区二区三区久久 | 久久99蜜桃精品久久久久小说 | 欧美日韩另类综合 | 四虎国产精品永久一区 | 国产美女久久久 | 狠狠干奇米 | 精品国产免费久久久久久 | 极品欧美人体xxxxoo | 99涩涩| 久久精品国产亚洲香蕉 | 久久综合一区二区三区 | 免费人成年短视频在线观看网站 |