集訓(xùn)隊作業(yè)二分答案法的應(yīng)用

1、二分上界（或）法的應(yīng)用前言：在 題目的的信息學(xué)競賽中，很多題目都令人無從下手，但如果先假定出法的應(yīng)用。，問題就立刻迎刃而解。下面從幾道例題談?wù)劧掷}一：草莓(noi2003)題意簡述：所有草莓重量的和（1 i k）。定義：sumi 表示第 i 塊草莓你的任務(wù)就是要把一片草莓田分割成k 塊，且分割方案需要滿足如下的條件：每一塊中的草莓必然是通過觸須直接或者間接和其他草莓相連接的；這種分割方案所對應(yīng)的x 盡可能的大。最后輸出你的分割方案和結(jié)果。算法分析：這是一道結(jié)果提交類問題，其中有 6 個數(shù)據(jù)都是樹，現(xiàn)在行。對樹進(jìn)初一看，這題很難找到有效的模型，關(guān)鍵在于有的時候切出 sum 很大的一塊反而不好

2、，因為題目中需要的是相對平均，因此，純粹的貪心很難成立。試著稍微改變一下題目，假設(shè)題目要求求一種不小于x 的方法，我們該如何處理呢？很快有了頭緒，首先通過寬度搜索建樹，然后從葉子結(jié)點開始向上處理，如果有以某個結(jié)點為根的的權(quán)值和超過了 x，就將該結(jié)點以及它所在的作為通塊，從圖中刪去。這樣的做法一定是正確的，的結(jié)點給這個連通塊顯然是沒有必要的。一因為 sum 一旦超過了x，如果把直進(jìn)行這樣的處理，如果割出了k 個連通塊以上，則問題有解，否則問題無解。因為只要掃描一遍，因此這個問題的時間復(fù)雜度為 O(N)。既然已經(jīng)可以在 O(N)的時間類解決上述子問題，那么能比較高效地求解原題呢？可以枚舉每一個x

3、再加以判斷，這樣復(fù)雜度較高。比較好的方法是采用二分法，假如一個解在某個去間a，b，首先判斷(a+b)/2 是否可行，如果可行，則枚舉(a+b)/2+1,b，否則枚舉a,(a+b)/2-1。那么，只需判斷 logm次即可（其中m 為所有點的權(quán)值和）。如果不知道 x，可不可以用上面的方法呢？下部分的情況，所以無法在恰當(dāng)?shù)臅r候是否定的，因為你不知道剩的選擇。復(fù)雜度分析：時間復(fù)雜度：O(NlogM)空間復(fù)雜度：O(N)備注：以上算法并不是嚴(yán)格的多項式算法，因為與權(quán)值有關(guān)，本題有多項式算法，但實際效果比以上算法略差，詳細(xì)參加同學(xué)的。例題二：神秘的山(UVA10122)題意簡述一座山有n 個山峰，有 n

4、個隊員要攀登這些山峰，每個隊員都選擇不同的山攀登。隊員必須從某整點開始攀登，線路為直線，且不能在空中飛_。下圖就是一種可行方案每個隊員的速度是一定的，現(xiàn)在要求上山峰。案，在最早的時候讓全員都攀登算法分析：首先求出每個隊員攀登到每個山峰所需要的時間，因為這些隊員總是要在整點處攀登，用最簡單的枚舉來實現(xiàn)這一步：枚舉一個點并加以判斷。這樣，很容易得到所需的信息。問題的關(guān)鍵是得到信息之后如何進(jìn)行下一步的處理。顯然，得到的是一個二分圖，而每條邊都值，二分圖最佳匹配？最佳匹配所求的是總的權(quán)值和最小，而這題僅僅是要求權(quán)值最大的邊最小，兩者間有著一定的差異，而且并不容易相互轉(zhuǎn)化，看來最佳匹配很難應(yīng)用于在本題上

5、。先將問題簡化，如果是求一個不超過q 的方案，有沒有方法呢？有！而且相對很容易的，因為如果一個隊員a 攀登山峰b 所需要的時間超過q，實際等價于這個隊員無法攀登上山峰b，因此，就要在原先的二分圖中刪去有些無用的邊， 重新構(gòu)圖，如果隊員a 能在q 時間內(nèi)攀登上山峰b，就在二分圖a,b 兩個頂點間連一條無向邊。新圖構(gòu)造完成后，如果在新圖中找到了一個完備匹配，則這可以作為一組可行方案，如果無法找到，則問題一定無解。在解決了這個簡化后之后，回到原先的題目。首先，可以定一個上界，如果可以找到一個可行方案，則可以將上界降低，否則將向上增加，直到找到一個方案為止。這一步可以通過二分來實現(xiàn)，顯然，最終的一定為

6、某個邊的權(quán)，因此，需要對邊權(quán)離散化，這樣可以減少二分的次數(shù)。復(fù)雜度分析時間復(fù)雜度：O(N3logM)空間復(fù)雜度：O(N2)例題三：最大平均數(shù)問題(usaco)題意簡述：給一個數(shù)列，在其中選出連續(xù)的一端數(shù)字（數(shù)字個數(shù)不小于 f），滿足這一段的平均數(shù)最大。例如數(shù)列 3 4 2 3 4 5 6 ，f=3，則選擇最后三個數(shù)字 4 5 6，它們的平均數(shù)是最大的。算法分析：如果用最簡單的枚舉，即使用部分和技術(shù)優(yōu)化，時間復(fù)雜度也高達(dá) O(N2)，無法讓人接受。貪心法是否可行呢？經(jīng)過嘗試，幾種貪心算法都被一一否決了，問題的關(guān)鍵是無法準(zhǔn)確的知道一個數(shù)字對平均數(shù)影響有多大，因為平均數(shù)總是不短變化中的。既然這個無法

7、解決，不妨做一個大膽的嘗試，如果把平均數(shù)固定，將問題轉(zhuǎn)化為能否找到一段數(shù)字，使它們的平均數(shù)超過q，是否能找到有效算法呢？首先一組解，否則找到最初的 f 個數(shù)字，如果它們的平均數(shù)不小于 q，那么就得到了繼續(xù)往后面掃描。填加下個數(shù)到當(dāng)前數(shù)列中，如果數(shù)列開頭的數(shù)字比q 小，則它的存在已經(jīng)沒有任何價值了，其從數(shù)列中刪去。接著，下一個數(shù)加入數(shù)列，再對面前的數(shù)進(jìn)行掃描。假設(shè)已經(jīng)處理到了第 p個數(shù)，那么如果前p-m 個數(shù)的平均數(shù)小于q，則 3 4 2 3 4 5 6 為例進(jìn)一步說明本算法。假設(shè)可以將他們刪去。下面以平均數(shù)定為 4：可見，當(dāng)平均數(shù)固定以后，可以很明確的知道一列數(shù)對平均數(shù)是否有貢獻(xiàn)，那么，就可以

8、很輕松的作出決策了。回到原題可以不斷枚舉平均數(shù)，看在該平均數(shù)下是否能找到可行方案，數(shù)列加入數(shù)字新數(shù)列操作3 4 233 4 2 3開頭的 3 小于 4，從數(shù)列中刪去4 2 344 2 3 4開頭數(shù)列不小于平均數(shù)，不作處理4 2 3 454 2 3 4 5開頭數(shù)列 4 2 平均數(shù)小于 3，刪去3 4 563 4 5 6平均數(shù)大于 4，結(jié)束如果可以找到，則將平均數(shù)向上增加，否則將平均數(shù)降低，之后進(jìn)行同樣的處理，直到確定。這一步通過二分來實現(xiàn)。復(fù)雜度分析：時間復(fù)雜度 O(NlogM)空間復(fù)雜度 O(N)備注事實上，本題有線形算法（參見遠(yuǎn)高于上述算法。），但實現(xiàn)較為煩瑣，思考難度也小結(jié)：本題確定平均數(shù)

9、后，可以將一個數(shù)對平均數(shù)的影響由“相對”變?yōu)椤敖^對”。例題四： fence rail(usaco)題意簡述：給 n 個物品和 m 個背包，每個物品都有體積，而背包也有相應(yīng)的容積，要求將盡量多的物品放入背包中，求一種可行方案。算法分析：本題沒有多項式算法，可以用搜索來解決。普通的想法是枚舉每個物品分別放入哪些背包，顯然這樣做時間復(fù)雜度就太高了須對這一算法進(jìn)行優(yōu)化。但在原算法的基礎(chǔ)上很難加入有效的優(yōu)化。使用跟上面幾道例題一樣的分析方法，先將題目簡化，如果題目求能否放入k 個物品，是不是就容易優(yōu)化了呢？首先，肯定是嘗試將最小的k 個物品放如背包中，這樣就不必像以前那樣盲目地選擇物品了。可以算出這k

10、個物品的體積以及背包的剩余容積，如果剩余容積以放入全部物品，則繼續(xù)搜索下去顯然是沒有意義的。從最大的物品開始按體積大小依次將物品放入背包（這樣做是因為體積小的物品跟便于調(diào)整，有利于可以更快的找到方案），如果某個背包剩余的體積連當(dāng)前最小的物品都放不下，則它的剩余容積從總剩余容積中減去。另外，還需要對物品進(jìn)行“有序化”，如果兩個物品體積相同，在搜索后一個物品的時候一定將它放一個物品的后面，這樣可以減少搜索量。經(jīng)過以上優(yōu)化之后，程序就能很快判斷出問題是否解了?；氐皆}，可以通過枚舉k，判斷是否能找到可行方案，再適當(dāng)?shù)卦鰷pk，這同樣可以同二分實現(xiàn)。小結(jié)：本題通過二分可以使確定放入哪些物品，同時有利于加入一些優(yōu)化?？偨Y(jié)：二分法往往需要與其他一些算法相結(jié)合，且它的時間復(fù)雜度經(jīng)常與題目中的某