小Hi和小Ho正在玩這樣一個(gè)游戲，在每局游戲的開始，小Hi手持一瓶可以認(rèn)為是無(wú)窮無(wú)盡的飲料，而小Ho手中有一個(gè)空杯子。
一局游戲分為N輪，在每輪行動(dòng)中，小Hi先向小Ho手中的杯子倒入T個(gè)單位的飲料（倒入的數(shù)量在一局游戲開始之前約定好且在整局游戲中固定），然后小Ho擲出一個(gè)均勻的K面骰子得到一個(gè)1..K之間的數(shù)d，如果杯中飲料的單位數(shù)小于等于d，則小Hi記一分，且小Ho將杯中剩余飲料一飲而盡，否則小Ho記一分，小Ho喝掉杯中d個(gè)單位的飲料。在N輪結(jié)束后，分高者獲勝。
那么問題來(lái)了，如果小Ho能夠預(yù)測(cè)這局中每輪自己所擲出的點(diǎn)數(shù)，那么最小的能使得小Ho獲勝的T（每輪小Hi倒入小Ho杯子的飲料的單位數(shù)）是多少？
算法分析本題需要我們求的是最小滿足要求的?T?值，使得在該?T?值下，小Ho獲得的分?jǐn)?shù)高于小Hi。
因?yàn)樾i和小Ho分?jǐn)?shù)之和一定為?n，所以小Ho獲勝的條件可以改為小Ho的分?jǐn)?shù)score大于n/2。
通過分析題意，我們可以知道score和?T?之間滿足一定的關(guān)系，score會(huì)隨著?T?值的變化而變化，則可以假設(shè)有：
score = f(T)
我們根據(jù)題目描述的游戲規(guī)則構(gòu)造出f(T)函數(shù)：
f(T):
rest = 0; // 當(dāng)前杯中剩余的飲料體積
score = 0; // 小Ho的得分
for i = 1 .. n
rest = rest + T; // 小Hi向杯子中倒入T單位飲料
if (rest > d[i]) // 若杯子中飲料大于第i輪的d
score = score + 1; // 小Ho獲得一分
rest = rest - d[i]; // 小Ho喝掉d個(gè)單位飲料
else
rest = 0; // 小Ho喝掉全部的飲料
end if
end for
return score;
每次執(zhí)行f(T)函數(shù)花費(fèi)的時(shí)間代價(jià)為?O(n)。
對(duì)f(T)進(jìn)一步研究，我們可以發(fā)現(xiàn)：
score = f(0) = 0當(dāng)?T = K?時(shí)，score = f(K) = n
我們可以猜想在?T?從?0?到?K?的過程中，小Ho獲得的分?jǐn)?shù)score是單調(diào)遞增的。
而要證明f(T)函數(shù)確實(shí)滿足遞增的性質(zhì)，只需證明對(duì)于?T?和?T'?(T?
我們?cè)O(shè)s[i]，r[i]表示第i輪開始，還沒有添加?T?單位飲料時(shí)，小Ho的得分和剩余飲料的體積；s'[i]，r'[i]表示第i輪開始，還沒有添加?T'?單位飲料時(shí)，小Ho的得分和剩余飲料的體積。
我們要證明：對(duì)于i?=?1..N+1，都有s[i]
≤ s'[i]且r[i] ≤ r'[i]。
利用數(shù)學(xué)歸納法，i?=?1?時(shí)，s[i]
= s'[i] = 0，r[i] = r'[i] = 0，結(jié)論成立。
假設(shè)i?=?n?時(shí)結(jié)論成立，那么當(dāng)i?=?n+1?時(shí)：r[n+1]
= max(r[n]+T-d, 0),r'[n+1] = max(r'[n]+T'-d, 0)。
由于r[n] ≤ r'[n]，T < T'，所以r[n]+T
< r'[n]+T'
d < r[n]+T < r'[n]+T時(shí)，r[n+1]
= r[n]+T-d,?r'[n+1] = r'[n]+T'-d,?s[n+1]
= s[n]+1,s'[n+1] = s'[n]+1，易知結(jié)論成立；當(dāng)r[n]+T ≤ d < r'[n]+T時(shí)，r[n+1]
= 0,?r'[n+1] = r'[n]+T'-d > 0,?s[n+1]
= s[n],s'[n+1] = s'[n]+1，易知結(jié)論成立；當(dāng)r[n]+T < r'[n]+T ≤ d時(shí)，r[n+1]
= r'[n] = 0,?s[n+1] = s[n],?s'[n+1]
= s'[n]，易知結(jié)論成立。
綜上所述，對(duì)于i?=?1..N+1，都有s[i]
≤ s'[i]且r[i] ≤ r'[i]。而f(T)
= s[N+1] ≤ s'[N+1] = f(T')，所以函數(shù)f(T)是單調(diào)遞增的。
當(dāng)score首次超過n/2時(shí)的?T?值，也就是我們要求的最小值，不妨記為?M。
那么接下來(lái)要考慮的就是如何快速的求得?M?值。
一個(gè)簡(jiǎn)單的想法是從?0?開始依次枚舉，直到score大于n/2，這樣可以保證在第一時(shí)間計(jì)算出?M值。一共需要執(zhí)行?M?次f(T)函數(shù)，所以其時(shí)間復(fù)雜度為?O(nM)。對(duì)于足夠強(qiáng)的數(shù)據(jù)這顯然是會(huì)超時(shí)的，必須降低執(zhí)行f(T)函數(shù)的次數(shù)。
我們?cè)僖淮斡^察f(T)函數(shù)：
我們隨機(jī)找一個(gè)?T?值，并計(jì)算出其f(T)。根據(jù)f(T)與n/2的大小關(guān)系，我們可以判斷出當(dāng)前計(jì)算出的?T?值是小于?M，亦或是大于?M。
由這個(gè)性質(zhì)，我們可以得到一個(gè)區(qū)間逼近的算法：
初始化?T?可能的取值區(qū)間[left, right]，保證f(left)
< n/2, f(right) ≥ n/2。這里我們?nèi)?code style="font-family:Menlo, Monaco, Consolas, 'Courier New', monospace;font-size:12.6000003814697px;color:rgb(199,37,78);background-color:rgb(249,242,244);">[0,M]。若left + 1 == right，跳轉(zhuǎn)第四步。否則繼續(xù)第三步。
取?mid = (left +
right) / 2，并計(jì)算出f(mid)。
假設(shè)f(mid) < n/2，由f(T)為單調(diào)遞增函數(shù)，則對(duì)于任意一個(gè)?T?屬于[left,
mid]，f(T) < n/2。
因此?M?一定不在[left,
mid]內(nèi)，M?一定在[mid, right]的區(qū)間內(nèi)。因此我們令left
= mid，并回到第二步。
同理，若f(mid) ≥ n/2，則?M?一定在[left,
mid]。此時(shí)我們令right = mid，并回到第二步。
left + 1 == right，且f(left)
< n/2, f(right) ≥ n/2。因此right即為所求的?M?值。這個(gè)算法滿足每一次將區(qū)間縮小一半，因此總的時(shí)間復(fù)雜度為?O(nlogK)。其偽代碼：
left = 0;
right = K;
while (left + 1 < right)
mid = (left + right) / 2;
if (f(mid) < n/2) left = mid;
else right = mid;
end while
至此我們得到了該題的解決辦法：利用二分縮小答案的區(qū)間，并利用答案本身去判定最優(yōu)解的范圍。
這樣的算法我們一般稱之為"二分答案"，其明顯的標(biāo)志有兩個(gè)：
求可行解中的最優(yōu)解能夠構(gòu)造出關(guān)于解的f(T)函數(shù)，并且f(T)函數(shù)滿足單調(diào)性只要能夠熟練的發(fā)現(xiàn)這兩個(gè)標(biāo)志，對(duì)于同類的問題也就能夠迎刃而解了。
下載文檔
