從Cash談一類分治算法的應(yīng)用

1、2008年信息學(xué)國家集訓(xùn)隊(duì)作業(yè)雅禮中學(xué)陳丹琦從Cash談一類分治算法的應(yīng)用分治算法的基本思想是將一個(gè)規(guī)模為 N的問題分解為K個(gè)規(guī)模較小的子問 題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同.求出子問題的解，就可得到原問題的解分治算法非?；A(chǔ)，但是分治的思想?yún)s非常重要，本文將從今年NOI的一道動(dòng)態(tài)規(guī)劃問題Cash開始談如何利用分治思想來解決一類與維護(hù)決策有關(guān) 的問題：例一.貨幣兌換（Cash）NOI 2007,貨幣兌換問題描述小Y最近在一家金券交易所工作.該金券交易所只發(fā)行交易兩種金券：A紀(jì)念券（以下簡稱 A券）和B紀(jì)念券（以下簡稱B券）.每個(gè)持有金券的顧 客都有 一個(gè)自己的帳戶.金券的數(shù)目可以是一個(gè)

2、實(shí)數(shù).每天隨著市場(chǎng)的起伏波動(dòng)，兩種金券都有自己當(dāng)時(shí)的價(jià)值，即每一單位金 券 當(dāng)天可以兌換的人民幣數(shù)目.我們記錄第K天中A券和B券的價(jià)值分別為Ak和Bk （元/單位金券）.為了方便顧客，金券交易所提供了一種非常方便的交易方式：比例交易 法.比例交易法分為兩個(gè)方面：A）賣出金券：顧客提供一個(gè)0, 100內(nèi)的實(shí)數(shù)OP作為賣出比例，其意 義 為：將OP%的A券和OP%的B券以當(dāng)時(shí)的價(jià)值兌換為人民幣；B）買入金券：顧客支付IP元人民幣，交易所將會(huì)兌換給用戶總價(jià)值為IP的金券并且淌足提供給顧客的A券和B券的比例在第K天恰好為Rat&例如，假定接下來 3天內(nèi)的Ak、Bk、Rate的變化分別為:時(shí)間A

3、kBkRAtek第一天11p第二天122第三天223假定在第一天時(shí)，用戶手中有 100元人民幣但是沒有任何金 券.用戶可以執(zhí)行以下的操作：時(shí)間用戶操作人民幣(元)A券的數(shù)量B券的數(shù)量開戶無100：°0第一天買入100元05050第二天賣出50%752525第二天買入60元155540第三天賣出100%20500注意到，同一天內(nèi)可以進(jìn)行多次操作.小Y是一個(gè)很有經(jīng)濟(jì)頭腦的員工，通過較長時(shí)間的運(yùn)作和行情測(cè)算， 他已經(jīng)知道了未來N天內(nèi)的A券和B券的價(jià)值以及 Rate.他還希望 能夠計(jì)算出來，如 果開始時(shí)擁有S元錢，那么N天后最多能夠獲得多少元 錢.算法分析不難確立動(dòng)態(tài)規(guī)劃的方程：設(shè)f i表示

4、第i天將所有的錢全部兌換成 A, B券，最多可以得到多少A券.很 容易可以得到一個(gè)O(n2)的算法：f 1 S * Rate1 / (A1 * Rate1 + B1)Ans SFor i 2 to nFor j 1 to i-1x f j * Ai + f j / Ratej * BiIf x > AnsThen Ans xEnd Forf i Ans * Ratei / (Ai * Ratei + Bi) End ForPrint(Ans)O(n2)的算法顯然無法勝任題目的數(shù)據(jù)規(guī)模.我們來分析對(duì)丁i的兩個(gè)決策j和k,決策j比決策k優(yōu)當(dāng)且僅當(dāng)：(f j -f k) * Ai + (f j

5、 / Ratej -f k / Ratek) * Bi > 0.不妨設(shè) f j < f k, gj = f j / Ratej,那么(gj - gk) / (fj - fk) < -ai / bi.這樣我們就可以用平衡樹以f j為關(guān)鍵字來維護(hù)一個(gè)凸線，平衡樹維護(hù)一個(gè)點(diǎn) 集(f j, gj), f j是單調(diào)遞增的，相鄰兩個(gè)點(diǎn)的斜率是單調(diào)遞減的.每次在平衡 樹中二分查找與-ai / bi最接近的兩點(diǎn)之間的斜率.這樣動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度就降低為O(nlog2n),但是維護(hù)凸線的平衡樹實(shí)在不容易在考場(chǎng)中寫對(duì)，編程復(fù)雜度高，不易調(diào)試(我的Splay代碼有6k多).這個(gè)問題看上去只能用高

6、級(jí)數(shù)據(jù)結(jié)構(gòu)來維護(hù)決策的單調(diào)性，事實(shí)上我們可以利用分治的思想來提出一個(gè)編程復(fù)雜度比較低的方法：對(duì)丁每一個(gè)i,它的決策j的范圍為1i-1 .我們定義一個(gè)Solve過程： Solve(l, r)表示對(duì)丁的l <i <r,用l <j <i-1的決策j來更新f i的值.這樣我們的 目標(biāo)就是Solve(1, n):可以先Solve(1, n/2)后計(jì)算出f 1 . fn/2,那么1n/2的每 一個(gè)數(shù)一定是n/2+1n的每個(gè)i的決策，用1n/2的決策來更新n/2+1n的fi 值后Solve(n/2+1, n).這恰好體現(xiàn)的是一種分治的思想：用1n/2的決策來更新n/2+1n的fi值：

7、類似用平衡樹的方法，我們可以 對(duì)1n/2的所有決策建立一個(gè)凸線，對(duì) n/2+1n的所有i按照-ai / bi從大到小 排序，凸線的斜率是單調(diào)的，-ai/bi也是單調(diào)的，這樣我們就可以通過一遍掃 描來計(jì)算出對(duì)丁每一個(gè)i在1n/2里面最優(yōu)的決策j.現(xiàn)在面臨的問題是如何對(duì)丁一段區(qū)間l, r維護(hù)出它的凸線：由丁 f 值是臨 時(shí)計(jì)算出來的，我們只需要遞歸的時(shí)候利用歸并排序?qū)⒚恳欢伟凑說 值從小到大排序，凸線可以臨時(shí)用一個(gè)棧 O(n)計(jì)算得出.下面給一個(gè)分治算法的流程：由丁-ai / bi是已知的，不像f i是臨時(shí)計(jì)算得出的.因此可以利用歸并排 序預(yù)處理，計(jì)算每一段l, r按照-ai / bi排序后的i.

8、ProcedureSolve(l, r)If l = rThen更新ans,利用已經(jīng)計(jì)算好的l的最優(yōu)決策k,計(jì)算f l值，ExitMid (l + r) / 2Solve(l, mid -1)對(duì)l, mid-1這一段掃描一遍計(jì)算出決策的凸線，由丁 mid+1 . r這一段以 -ai / bi的排序在預(yù)處理已經(jīng)完成，因此只需要掃描一遍更新 mid + 1 . r 的最優(yōu)決策.Solve(mid+1, r)利用l, mid-1已排好序的f 值和mid+1, r已排好序的f 值歸并排序?qū), r這一段按f值排序.End Procedure至此，問題已經(jīng)基本解決.時(shí)間復(fù)雜度為 T(n) = 2T(n/

9、2) + O(n),因此算法的 時(shí)間復(fù)雜度為O(nlog2n), NOI2007的測(cè)試數(shù)據(jù)最慢的測(cè)試點(diǎn) 0.2s,是一個(gè)相當(dāng) 優(yōu)秀的算法.我們比較一下分治算法和用平衡樹維護(hù)決策的方法：時(shí)間復(fù)雜度均為O(nlog2n)，空間復(fù)雜度平衡樹為 O(n),分治為O(nlog2n)(預(yù)處理-ai/bi需要 O(nlog2n)的空間).但是編程復(fù)雜度卻差別非常大，分治算法實(shí)現(xiàn)起來相當(dāng)簡單， 對(duì)丁考場(chǎng)來說無疑是一個(gè)非常好的方法.在編程復(fù)雜度非常高的情況下，動(dòng)態(tài)規(guī)劃維護(hù)決策與分治思想很好的結(jié)合起 來從而降低了編程復(fù)雜度，無疑是“柳暗花明乂一村”.這種分治思想主要體現(xiàn) 在將不斷變化的決策轉(zhuǎn)化成一個(gè) 不變的決策集

10、合，將在線轉(zhuǎn)化為離線.下面我們 再來看一個(gè)例題：例二.MokiaBalkan Olympiad in Informatics, 2007問題描述有一個(gè)W *W的棋盤，每個(gè)格子內(nèi)有一個(gè)數(shù)，初始的時(shí)候全部為0.現(xiàn)在要求維護(hù)兩種操作：1) Add:將格子(x, y)內(nèi)的數(shù)加上A.2) Query:詢問矩陣(X0, y0, xi, yi)內(nèi)所有格子的數(shù)的和.數(shù)據(jù)規(guī)模：操作 1) <160000,操作 2) < 10000, 1W 壬 2000 000.算法分析這個(gè)問題是IOI 2000 Mobile的加強(qiáng)版：Mobile中WW000,就可以利用二樹 狀數(shù)組在O(log22n)的時(shí)間復(fù)雜度內(nèi)

11、維護(hù)出操作1)和操作2).這個(gè)問題中W很大, 開二維樹狀數(shù)組O(W2)的空間顯然吃不消，考慮使用動(dòng)態(tài)空間的線段樹，最多可 能達(dá)到操作次數(shù)* (log2W)2個(gè)節(jié)點(diǎn)，也相當(dāng)大了.考慮使用分治思想來解決問題：將操作1)和操作2)按順序看成是一個(gè)個(gè)事件，假設(shè)共有Tot個(gè)事件，TotM70000.類似例題一，我們定義 Solve(l, r)表示對(duì)丁每一個(gè) Query操作的事 件i,將l .i-1的Add操作的所有屆丁 i的矩形范圍內(nèi)的數(shù)值累加進(jìn)來.目標(biāo)是 Solve(1, n).假設(shè)計(jì)算 Solve(L, R),遞歸 Solve(L, Mid), Solve(Mid + 1, r)后,對(duì) L . Mid 的所有Add操作的數(shù)值累加到Mid + 1 . R的所有匹配的Query操作的矩形中.后面這個(gè)問題等價(jià)?。浩矫嬷杏?p個(gè)點(diǎn)，q個(gè)矩形，每個(gè)點(diǎn)有一個(gè)權(quán)值，求 每個(gè)矩形內(nèi)的點(diǎn)的權(quán)值之和.這個(gè)問題只需要對(duì)所有的點(diǎn)以及矩形的左右邊界進(jìn) 行排序，用一維樹狀數(shù)組或線段樹在O(p+q)log2W)的時(shí)間復(fù)雜度即可維護(hù)得出. 因此問題的總的時(shí)間復(fù)雜度為O(Tot*log2Tot1og2W),不會(huì)高丁二維線段樹的O(Tot*log 2W*log 2W)的時(shí)間復(fù)雜度.上述這個(gè)算法無論是編程復(fù)雜度還是空間復(fù)雜度都比使用二維線段樹優(yōu)秀， 分治思想乂