|
2024/12/25 題目說明: 在一個群體征戰遊戲中， 任何一個弱者都是防線上很嚴重的缺口， 所以全體的戰鬥力由最弱者的戰鬥力決定， 遊戲玩家需要儘量將 n 個小兵的戰鬥力升級。 每個小兵升級 x 等需要 x2 個金幣， 現有 c 枚金幣， 請問全體的戰鬥力最多可以升級到幾等。下面第一個測試案例中總共有 3 個小兵， 戰鬥力分別是 2, 4, 6， 玩家擁有 10 枚金幣： 玩家可以將第 1 位的戰鬥力由 2 級升至 5 級需 32 枚金幣， 第 2 位的戰鬥力由 4 級升至 5 級需 12 枚金幣， 升級後戰鬥力分別是 5, 5, 6， 全體戰鬥力可以達到 5 級。
|
輸入測試資料一:
3 10↵ 2 4 6↵每一個測試案例有兩列輸入， 第一列有兩個正整數 n 與 c， n 為小兵數量 1<=n<=20000， c 為金幣數量 1<=c<=1014， 第二列有 n 個正整數 a1, a2, ..., an， 1<=ai<=107 為 n 個小兵目前個別的戰鬥力。
|
輸出測試資料一:
5↵每一個測試案例輸出一列， 包含一個正整數 p， 代表所有的小兵的戰鬥力都可以提升到 p 以上 (含 p)。
|
輸入測試資料二:
12 91456780↵ 41 49 10 38 20 10 5 0 2 41 45 15↵ 21 145678099↵ 13 5 71 72 65 9 41 58 10 26 39 31 3 40 55 38 33 72 27 25 29↵ 6 267↵ 25 39 36 17 20 39↵ 1 100000000000000↵ 10000000↵
|
輸出測試資料二:
2783↵ 2670↵ 29↵ 20000000↵
|
| 提示： 這是一個「最大化最小值」的問題， 是否可以得到某一個全體戰鬥力可以在計算之後明確判斷， 希望得到的全體戰鬥力在一定的範圍內， 最大的全體戰鬥力可以由擁有的金幣數量測試出來， 由於 c 與 n 的數量較大， 是一個標準的二分搜 (binary search) 問題。 |