Educational Codeforces Round 138 C. Number Game 簡便過法

根據(jù)題意,Bob add 過的元素不可能再被 Alice 選擇,所以Bob的操作也相當于刪除掉一個。
不難發(fā)現(xiàn),每次刪除最小的元素對于Bob來說是最優(yōu)的策略。因此只要排序,每次Bob刪掉最前面一個就行了。
對于Alice,題目所求是最大k,其最大取值一定不會超過(n + 1) / 2,考慮到 n 的范圍很小,所以直接枚舉即可。
接下來我們記 x = k - i + 1,
當 x = 0 時,也就意味著Alice獲得勝利,只要在此前從大到小枚舉k,這個時候直接輸出的k一定是最優(yōu)的;
當 x > 0 時,比賽尚未結束,Alice需要刪除一個元素,不難發(fā)現(xiàn),每次在數(shù)組中找到第一個小于等于x的元素,這樣的策略對于Alice來說是最優(yōu)的(如果找不到這樣的元素,則表示Alice輸了)