算法合集之一類算法復(fù)合的方法

1、一類算法復(fù)合的方法江蘇省揚(yáng)州中學(xué) 張煜承 摘要本文講了一類算法復(fù)合的方法。這種方法是指將一個(gè)問題的若干種算法，分 別使用于這個(gè)問題中若干個(gè)互補(bǔ)的部分。本文對(duì)兩個(gè)有意思的問題作了詳細(xì)的分析，使用了這種算法復(fù)合的方法成功解決了這兩個(gè)問題。問題一中我們將一個(gè)O()和一個(gè)O()的算法復(fù)合，分別使用于問題中的兩部分詢問，得到了一個(gè)O( )的算法。問題二中，我們將兩 個(gè)O()的算法使用于原問題分割得到的三部分，得到了一個(gè)O()的算法。 本文最后對(duì)這類方法進(jìn)行了總結(jié)。每個(gè)算法都可能有各自的優(yōu)勢(shì)和劣勢(shì)。而 將它們復(fù)合，使用于問題中的不同的部分，就有可能會(huì)將它們的優(yōu)勢(shì)結(jié)合起來，取長(zhǎng)補(bǔ)短，得出一個(gè)總體更優(yōu)的算法。

2、這種思想是極為重要的。關(guān)鍵字算法復(fù)合 方法一、問題一11.1 問題描述維護(hù)一個(gè)集合 S，初始時(shí)為空。對(duì)這個(gè)集合有兩種操作： 1、 B X 在集合 S 中插入一個(gè)整數(shù) X，保證當(dāng)前集合中 X 還不存在 2、 A Y 詢問集合 S 中，被 Y 除余數(shù)最小的數(shù)是多少。如果有多個(gè)數(shù)余數(shù)相1題目來源：The 2006 ACM Asia Programming Contest - Shanghai第 1 頁(yè)，共 11 頁(yè) 等，取任意一個(gè) 有 N 個(gè)操作需要依次處理。計(jì)算所有詢問的答案。允許離線算法。其 中 1 40000，1 , 5000001.2 初步分析這道題讓我們?cè)O(shè)計(jì)算法維護(hù)一個(gè)集合 。我們先考慮一

3、些容易想到的算法。最容易想到的算法是直接模擬問題中規(guī)定的操作，我們稱其為算法 1.0。每當(dāng)遇到一個(gè)詢問操作“A”時(shí)，我們枚舉當(dāng)前集合 中的每個(gè)數(shù)，從中找出被 除余數(shù)最小的。算法的時(shí)間復(fù)雜度為O 插入操作個(gè)數(shù) 詢問操作個(gè)數(shù) ，最壞情況 下顯然會(huì)超時(shí)。但當(dāng)插入操作很少或詢問操作很少時(shí)，這個(gè)算很快。 另一個(gè)略優(yōu)一些的算法也很容易想到（算法 1.1）。設(shè)()表示當(dāng)前集合 S 中使得 x mod y 最小的數(shù) x，也就是詢問“A y”的答案。因?yàn)樵试S離線算法，我們可以事先整理出詢問中所有不同的 Y 組成的集合 T，然后我們對(duì)每個(gè) 維護(hù)()的值。每當(dāng)插入一個(gè)數(shù)的時(shí)候，我們用O(| |)的時(shí)間逐個(gè)更新這些值

4、。算法 的時(shí)間復(fù)雜度為O 插入操作個(gè)數(shù) | | 。| |同樣是O( )級(jí)別的，所以也不能完 全解決問題。其實(shí)，這里的集合 T 可以理解為我們想維護(hù)的詢問。我們可以只維護(hù)一部分詢問中出現(xiàn)的 Y，維護(hù)需要的時(shí)間就會(huì)減少，但是將會(huì)有一些詢問得不到回答。 1.3 抓住問題的特征得出另一個(gè)算法（算法 1.2）為了解決這個(gè)問題，我們抓住問題的特征，深入思考。當(dāng)遇到一個(gè)詢問“A Y”的時(shí)候，我們要在當(dāng)前集合 S 中尋找使得 x mod Y 最小的數(shù) x 。我們把這里的 x 寫成 +， 其中0 ， 那么說明區(qū)間 , 中沒有在 S 中的數(shù)，否則 ( )就是區(qū)間 , 內(nèi)的最小數(shù)。圖 1.2 給出了一個(gè)具體的例子。

5、 22277777812121212+圖 1.2：這里，S 當(dāng)前為2,7,8,12，Y=5( )在方格的下方表示出來 很容易觀察到，對(duì)很多連續(xù)的 a， ( )是相等的。如果 S 為空，則對(duì)于任意的自然數(shù) a，( ) = +。否則我們把集合 S 中的數(shù)排序，得到. . . 的時(shí)候， 的時(shí)候，我們繼續(xù)使用算法 1.2；當(dāng) 的時(shí)候我們使用另一種算法。 算法 1.2 可以解決大多數(shù) Y 的詢問，剩下的 Y 會(huì)比較少。回想我們前面提出的算法 1.1，當(dāng)需要維護(hù)的 Y 很少時(shí)很好。所以當(dāng) 的時(shí)候，我們正好可以使用算法 1.1。此時(shí)我們令算法 1.1 中的集合 T 為1, ，也就是對(duì)1 的詢問維護(hù)答案。 因

6、此我們得出算法 1.3： 首先順序地處理操作，回答 的詢問。每次插入對(duì)每個(gè)1 更新 ( )， 需要O( )的時(shí)間?；卮鹈總€(gè) 的詢問顯然只需O(1)的時(shí)間。 然后倒序地處理操作，回答 的詢問。每次插入操作要把兩個(gè)集合合并， 需要O(1)的時(shí)間。詢問A Y 時(shí)，我們找O 個(gè)區(qū)間中的最小數(shù)，對(duì)每個(gè)區(qū)間 , ， 我們查找 a 所在的集合，需要O(1)的時(shí)間。因?yàn)?，詢問的時(shí)間復(fù)雜度為O 。 算法 1.3 的總時(shí)間復(fù)雜度為O + ，其中 K 是一個(gè)我們?cè)O(shè)的邊界值。 將 N 和 R看作常數(shù)，容易得出當(dāng) = 時(shí)總時(shí)間復(fù)雜度最小，為O 。本 題中 N 最大 40000，R=500000， 最大約為 28284

7、271，本算法可以完全解決 本題。1.5 小 結(jié)對(duì)這道題，我們先經(jīng)過初步思考，得出了兩個(gè)樸素算法：算法 1.0 和算法 1.1。 它們?cè)谀承┹斎胂聲?huì)有很好的表現(xiàn)，但最壞情況下都太慢了，不能完全解決問題。 第 5 頁(yè)，共 11 頁(yè) 需要注意的是，其中算法 1.1 當(dāng)| |很小，也就是需要維護(hù)的詢問很少時(shí)，會(huì)有很 好的表現(xiàn)。 然后我們抓住問題的特征，由使被一個(gè)數(shù)除余數(shù)最小入手，得出了算法 1.2。算法 1.2 當(dāng)詢問中的 Y 比較大的時(shí)候比較快，但仍然不能完全解決問題。 算法 1.1 和算法 1.2 單獨(dú)使用都不能完全解決問題，但是我們注意到它們可 以解決這個(gè)問題中兩個(gè)互補(bǔ)的部分。我們根據(jù) Y 的

8、大小，把詢問分成兩部分處理。 對(duì) 的詢問使用算法 1.1，對(duì) 的詢問使用算法 1.2。這樣做完全解決 了問題?？梢?，我們解決本題的重點(diǎn)是，不使用統(tǒng)一的算法，而是同時(shí)使用這個(gè)問題 的兩種算法，分別解決問題中的兩個(gè)互補(bǔ)的部分。二、問題二42.1 問題描述在一個(gè)平面上給定 N 個(gè)點(diǎn)。求以這 N 個(gè)點(diǎn)中的任意 4 個(gè)點(diǎn)為頂點(diǎn)，可以組成 多少個(gè)邊和坐標(biāo)軸平行的矩形。 其中1 250000。每個(gè)點(diǎn)的時(shí)限最多 30s。 2.2 初步分析雖然這道題的時(shí)限非常長(zhǎng)，但 N 最大為 250000。為了解決問題，我們預(yù)期要設(shè)計(jì)出一個(gè)時(shí)間復(fù)雜度低于O( )的算法。 因?yàn)榻M成矩形要求邊和坐標(biāo)軸平行，所以只是需要點(diǎn)的坐標(biāo)相

9、等，我們只關(guān)心坐標(biāo)的相對(duì)關(guān)系。所以我們可以把點(diǎn)的坐標(biāo)離散化。如圖 2.1，這樣我們會(huì)得到一個(gè)最壞情況大小N 的網(wǎng)格，輸入給定的點(diǎn)分布在網(wǎng)格的格點(diǎn)上。 4題目來源：MIT Individual Contest 2007，SPOJ RECTANGL第 6 頁(yè)，共 11 頁(yè) 圖 2.1：對(duì) 12 個(gè)點(diǎn)進(jìn)行離散化，得到了一個(gè)4 5的網(wǎng)格 顯然，組成矩形的 4 個(gè)點(diǎn)會(huì)有 2 個(gè)點(diǎn)在網(wǎng)格的一行，2 個(gè)點(diǎn)在網(wǎng)格的另一行上。因此，我們可以算出網(wǎng)格上每?jī)尚悬c(diǎn)組成的矩形的個(gè)數(shù)，最后把它們相加即 為答案。2.3 一個(gè)不難想到的算法一個(gè)O()的算法（算法 2.1）不難想到。我們分別以網(wǎng)格的每?jī)尚?, ( 1、2、3、

10、時(shí)，我們稱行 x 為 A 類，否則為 B 類。顯然問題就被分成了三部分： 以兩個(gè) A 類行中的點(diǎn)組成矩形，共有多少個(gè)矩形以兩個(gè) B 類行中的點(diǎn)組成矩形，共有多少個(gè)矩形 以一個(gè) A 類行和一個(gè) B 類行組成矩形，共有多少個(gè)矩形很容易注意到，A 類行的個(gè)數(shù)必然 ，所以 A 類行中的總點(diǎn)數(shù) = 。而事實(shí)上 A 類行中點(diǎn) 的個(gè)數(shù)必然 ，矛盾。 有了 A 類行的個(gè)數(shù)比較少這個(gè)限制，我們就可以對(duì)部分 1 使用算法 2.1。 注意到算法 2.1 中，我們只要先枚舉一行，另一行的枚舉在時(shí)間復(fù)雜度上相當(dāng)于把所有的點(diǎn)都掃描一遍。這就允許我們?cè)谔幚聿糠?1 時(shí)，“順便”處理部分3，并且不影響時(shí)間復(fù)雜度。 而對(duì)部分

11、2，我們有了一個(gè)新的限制，即每行中的點(diǎn)數(shù) ，也就是說，每行中的點(diǎn)數(shù)會(huì)比較少。我們抓住問題的特征，也就是這個(gè)限制，設(shè)計(jì)一個(gè)針對(duì)每 行中點(diǎn)數(shù)較少時(shí)比較優(yōu)的算法。2.5 對(duì)部分 2 設(shè)計(jì)另一個(gè)算法（算法 2.2）部分2 中每行中的點(diǎn)數(shù)較少也就意味著，以每行中任意兩個(gè)不同的點(diǎn)為端點(diǎn)， 組成的線段的個(gè)數(shù)也較少。以一個(gè)點(diǎn)作為線段 l 的右端點(diǎn)，因?yàn)橐恍凶疃嘤?K 個(gè)點(diǎn)，線段 l 的左端點(diǎn)可以有O( )個(gè)選擇。那么以所有的O( )個(gè)點(diǎn)作為右端點(diǎn)， 會(huì)有O( )條線段。 第 8 頁(yè)，共 11 頁(yè) 圖 2.3：線段2,4出現(xiàn)了 2 次，即圖中的兩條黑線 顯然，將所有的行上的線段放在一起，對(duì)每種線段 , 統(tǒng)計(jì)它出

12、現(xiàn)的次數(shù) s。這里的 a 和 b 是指同一行上兩個(gè)點(diǎn)的列號(hào)。容易得出答案就是 C 。統(tǒng)計(jì)這樣的線段出現(xiàn)的次數(shù)，很容易想到可以使用 hash，時(shí)間復(fù)雜度為O( )。但注意到空間復(fù)雜度同樣為O( )。 不難想到一個(gè)減小空間復(fù)雜度的方法是：先確定線段的右端點(diǎn) b，然后將所有右端點(diǎn)為 b 的線段放在一起考慮，把它們的左端點(diǎn)放進(jìn) hash。 因?yàn)楝F(xiàn)在只要 hash 一個(gè)端點(diǎn)，所以空間被降到了O( )。而每個(gè)點(diǎn)和原來一 樣都只被當(dāng)作右端點(diǎn)考慮了一次，因此時(shí)間復(fù)雜度不變，為O( )。 2.6 問題的解決至此 3 個(gè)部分都得到了較好的解決，我們將它們合并起來考慮。對(duì)部分 1 和 部分 3 我們使用算法 2.1

13、，時(shí)間復(fù)雜度為O 。對(duì)部分 2 我們使用算法 2.2，時(shí) 間復(fù)雜度為O( )?？倳r(shí)間復(fù)雜度為O + 。當(dāng) K 取 . 時(shí)，時(shí)間復(fù)雜度 達(dá)到最小，為O( . )，可以解決本題。 2.7 小 結(jié)我們經(jīng)過簡(jiǎn)單的初步分析后，很輕松地得出了算法 2.1。它不能完全解決問題，但當(dāng)行數(shù)比較少的時(shí)候會(huì)很好。我們根據(jù)算法 2.1 的這個(gè)優(yōu)勢(shì)，把問題按每行點(diǎn)數(shù)的多少分成了 3 部分。對(duì)部分 1 和部分 3 我們是使用算法 2.1。而對(duì)部分第 9 頁(yè)，共 11 頁(yè) 2，我們根據(jù)它的特征，設(shè)計(jì)出了一種針對(duì)這部分很快的算法 2.2。然后我們同時(shí) 使用算法 2.1 和算法 2.2，得到了一個(gè)總時(shí)間復(fù)雜度O()的算法，解決

14、了問題。而.假如我們單獨(dú)使用算法 2.1 或算法 2.2，都將得到最壞情況下O()的算法， 不能完全解決問題?？梢娺@種算法復(fù)合的方法在本題的解決中的重要性。 本題和問題一一樣，都是將兩種相對(duì)簡(jiǎn)單的算法進(jìn)行了復(fù)合，使用于問題的 不同部分，但部分的劃分沒有上一題那么明顯。能這樣將問題進(jìn)行劃分，需要我 們敏銳的觀察力和扎實(shí)的基本功。三、總結(jié)一個(gè)問題往往可以被看作是由若干個(gè)部分組成起來的。注意這里所說的部分是相對(duì)并列的。我們通常對(duì)這些部分使用統(tǒng)一的算法。而有時(shí)這個(gè)問題可以使用 多種算法解決，并且當(dāng)這些算法應(yīng)用在問題中不同特征的部分時(shí)，會(huì)有不同的效 果。這時(shí)我們就可以將這些算法復(fù)合，對(duì)問題的不同部分，根

15、據(jù)它們的特征分別 選擇使用對(duì)這個(gè)部分較優(yōu)的算法。這就是本文所講的算法復(fù)合的方法。對(duì)本文中的兩個(gè)問題，我們都使用了這種方法。問題一中我們得出了兩個(gè)最 壞情況分別是O()和O()的算法。它們都不能解決問題，但它們分別針對(duì)問題的兩個(gè)部分會(huì)有很好的效果。于是我們對(duì)問題的兩部分分別使用這兩種算法， 最終得到了O 的算法，使問題得到了較好的解決。問題二與之類似，我們將兩個(gè)最壞情況下O( )的算法復(fù)合起來，得到了一個(gè)O( . )的算法。 我們注意到兩個(gè)算法合并起來后，我們很“神奇”地得到了一個(gè)更優(yōu)的算法。 這是因?yàn)檫@兩種算法具有互補(bǔ)的優(yōu)勢(shì)，而我們把問題分成了若干部分，對(duì)每一部 分根據(jù)其特征使用較優(yōu)的算法，就使得兩種算法的優(yōu)勢(shì)得到了結(jié)合。每個(gè)算法都有各自的優(yōu)勢(shì)和劣勢(shì)。如果我們?nèi)￠L(zhǎng)補(bǔ)短，充分利用它們的優(yōu)勢(shì)， 也許就將會(huì)得出總