A. GamingForces

Monocarp 正在玩一個電腦游戲，需要殺死 n 只怪獸，每只怪獸有一個生命值?,Monocarp 有兩種技能，第一種是選擇兩只怪獸，各扣一滴血，第二種是選擇一只怪獸，直接殺死，問 Monocarp 最少需要釋放幾次技能才能殺死所有怪獸。

思路：

首先對于所有生命值為 1 的怪獸，肯定是釋放第一種技能比較好，因為釋放一次最多能殺死兩只，釋放??次就可以殺死所有生命值為 1 的怪獸，而對于生命值不為 1 的怪獸，肯定是選擇直接殺死更優(yōu)，因為兩次第一種技能可能不一定能殺死兩只怪獸，但是兩次第二種技能一定能殺死兩只怪獸。因此需要釋放的技能次數(shù)為：，其中 one_cnt 是生命值為 1 的怪獸的數(shù)量，除法是整除。

B. Stand-up Comedian

Eve 是一個入門喜劇表演家，她準(zhǔn)備了四類節(jié)目，分別有???個，現(xiàn)在她要邀請朋友 Alice 和 Bob 來欣賞她的表演。A 和 B 初始時有一個情緒值 0，觀看到不喜歡的表演，情緒值會減一，看到喜歡的表演，情緒值會加一，當(dāng)某個人情緒值小于 0，那么就會離開。在Eve 準(zhǔn)備的四類節(jié)目中，第一類是 A 和 B 都喜歡的，第二類是 A 喜歡 B 不喜歡，第三類是 A 和 B 都不喜歡的。問 Eve 在 A 和 B 有人離開之前最多能表演多少節(jié)目。?

思路：

首先肯定直接表演第一類節(jié)目，A 和 B 的情緒值都變?yōu)?. 接著，注意到表演的節(jié)目數(shù)量是受制于兩人中情緒值低的，而第二類和第三類節(jié)目都屬于此消彼長的類型，因此應(yīng)該先平衡兩人的情緒值，第二類和第三類節(jié)目輪流表演，可以表演? 個節(jié)目，然后兩人的情緒值仍然和初始相同。接著可以表演第四類節(jié)目，如果?，那么最多再表演? 個節(jié)目，如果?，那么可以先表演完第四類節(jié)目，然后再表演剩下的第二或第三類節(jié)目，有? 個，如果?，那么就表演完了所有節(jié)目，否則，可以再表演? 個節(jié)目，到此就結(jié)束了。

但是需要注意的是，如果一開始第一類節(jié)目的數(shù)量是 0，那么就沒有后面的步驟了，因此需要特判。

C. Min Max Sort

給出一個數(shù)字 1 - n 的排列，可以對它進行任意次如下操作：任選兩個元素 x, y，把其中小者移動到排列頭部，大者移動到排列尾部。問經(jīng)過至少多少次這樣的操作，排列按照升序排列。

思路：

首先構(gòu)造性地給出一個方法，對于任意排列，用? 次一定能完成：每次選擇最靠近 1 - n 的中位數(shù)且之前沒被選中過的兩個數(shù)，直到最后一步選擇 1 和 n. 接下來來看操作序列的性質(zhì)，反著來看，最后一步一定選擇的是 1, n, 前一步是 2, n-1, 以此類推，如果 k 步操作之后排列是單調(diào)遞增的，那么有這樣的性質(zhì)：把最后 k 步選擇的元素都刪除，剩下的是一個有序的序列。而且我們知道，如果一個 k 滿足這樣的性質(zhì)，那么 k+1, k+2, .... 也滿足這樣的性質(zhì)，因此存在單調(diào)性，可以二分答案。每次 check 只需要判斷刪除了前 k 小和前 k 大的元素之后，剩下的元素是否有序即可。