Edu CF Round 138 - B & C
??? 最近開始刷一點(diǎn) CF 上的 Edu Round，平常每天寫個一兩題。算法水平太菜大概只寫 ABCD，隨手寫一點(diǎn)題解記錄一下。?
B. Death's Blessing
??? 題意大概是一堆 monster 線性排列，每個 monster 有兩個屬性 health 和 strength，其中 health 代表玩家殺死它需要的時間，strength 代表它死后會給它直接相鄰的 monster 的 health 增加的數(shù)值。求殺死所有 monster 最少需要的時間。
??? 用 表示第 i 個 monster 的 health，
表示第 i 個 monster 的 strength.
思路:
??? 首先需要明確，殺死 monster 的順序會影響最后的用時，因此就是要確定一個最優(yōu)的順序，使得殺死所有的時間最小。因?yàn)樽詈笠獨(dú)⑺浪械?monster，因此 肯定在答案中，現(xiàn)在考慮哪些
會對最后的答案有貢獻(xiàn): 除了最后被殺死的 monster 之外，其他的 monster 對應(yīng)的 strength 都會至少貢獻(xiàn)一份在答案中，這構(gòu)成最后答案的一個下界。而殺死兩邊的 monster 只會貢獻(xiàn)一倍的 strength，殺死中間的會貢獻(xiàn)兩倍，因此要貪心地做，每次都挑選兩邊的來殺死，直到留下?lián)碛凶畲?strength 的 monster 最后殺死。
??? 因此最后的答案其實(shí)可以很直接的算出來: ，直接
算出來。
C. Number Game
??? 題意大概是 Alice 和 Bob 兩個人玩游戲，在一個一維數(shù)組上操作，數(shù)組中有 n 個元素，每局游戲需要選擇一個 k，每個游戲?qū)掷m(xù) k 個 stage，標(biāo)號從 1 到 k，在第 i 個 stage，A 會從數(shù)組中刪除一個小于等于 k - i + 1 的數(shù)，B 會給一個元素加上 k - i + 1，如果在某個回合開始的時候 A 沒有元素可以刪了，那么 A 輸，如果第 k 回合結(jié)束 A 還沒輸，那么 B 輸。問給定數(shù)組，A 可以贏的最大的 k 是多少，假設(shè) A 和 B 都進(jìn)行 optimal 的操作。
思路:
??? 首先注意到這里的 k 有一個單調(diào)的性質(zhì)，即: 如果某個 k 可以使得 A 贏得游戲，那么比這個 k 小的值也一定可以，這個性質(zhì)是顯然成立的，因?yàn)橹恍枰绨巡僮餍蛄薪財嗑蜆?gòu)成更小的 k 的時候的操作方案。有了這個單調(diào)的性質(zhì)，可以考慮二分來求。問題變?yōu)槿绾闻袛嘁粋€給定的 k 是否能夠讓 A 贏。
??? 注意到，B 每次會給某個元素加上 k - i + 1，這會使得被加的這個元素在之后的游戲中都無法被 A 刪除，因此 B 每次加最小的元素肯定是不虧的。而對于 A 來說，每個回合選擇當(dāng)前能夠刪除的最大元素一定是最優(yōu)的操作之一，這可以通過交換論證來說明。
??? 要讓 A 最后勝利，只需要讓 A 在第 k 回合開始的時候還有元素可刪，根據(jù)上述的方案，第 k 回合開始的時候，B 已經(jīng)刪除數(shù)組的最小的 k-1 個元素，因此只需要檢查數(shù)組的第 k 到 2k-1 大元素這一段是否能夠讓 A 從第 1 回合操作到第 k 回合。如果記 為這一段數(shù)組中小于等于 i 的元素的個數(shù)，那么就是需要滿足
. 判斷這個性質(zhì)可以在
之內(nèi)完成。
??? 因此，對于每一組數(shù)據(jù)，可以在 內(nèi)求出最大的 k.
