題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC457D Raise Minimum

Problem Statement

題目簡述

給定一個長度為 $N$ 的整數序列 $A = (A_1, A_2, \ldots, A_N)$ 與整數 $K$ 。
可以進行 $0$ 到 $K$ 次操作，每次選擇一個滿足 $1 \leq i \leq N$ 的整數 $i$ ，並將 $A_i$ 加上 $i$ 。
求操作後序列中 $\displaystyle \min_{1 \leq i \leq N} A_i$ 的最大可能值。

Constraints

約束條件

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^{18}$
$1 \leq K \leq 10^{18}$
所有輸入皆為整數

思路：二分答案

這題要最大化「所有元素中的最小值」。如果直接模擬每一次操作，會卡在操作次數可能很大；但我們其實不需要知道每一步怎麼做，只需要判斷某個候選最小值能不能被達成。

關鍵觀察

若某個目標值可以達成，那麼比它更小的目標值一定也可以達成；若某個目標值無法達成，那麼比它更大的目標值也一定無法達成。

這種「可行 / 不可行」具有單調性的答案空間，正適合用二分搜尋。

如何檢查一個目標值

假設現在想讓所有元素都至少變成某個目標值。對於已經不小於目標值的元素，不需要做任何事；對於還不夠大的元素，就必須補足差距。

第 $i$ 個元素每操作一次可以增加 $i$ ，因此若它距離目標值還差 $d$ ，至少需要

\left\lceil \frac{d}{i} \right\rceil

次操作才能補到目標值以上。把所有不足元素需要的操作次數加總，如果總和不超過 $K$ ，代表這個目標值可行；反之不可行。

向上取整不要用浮點數

這裡的數值可能很大，用浮點數計算 ceil 可能產生精度問題。
整數形式可以寫成：

\left\lceil \frac{d}{i} \right\rceil = \frac{d+i-1}{i}\text{ 的整除結果}

二分範圍

答案的下界可以從目前陣列的最小值開始，因為即使不做任何操作，最小值也至少是這個數。

答案的上界可以用「把所有操作都集中在某一個元素上」後，各元素各自能到達的最大值取最小：

\min_i(A_i + iK)

真正的答案不可能超過這個值，因為任一元素最多也只能被操作 $K$ 次。

複雜度分析

時間複雜度： $\mathcal{O}(N \log V)$ ，其中 $V$ 是答案二分的值域大小。
空間複雜度： $\mathcal{O}(1)$ ，除了輸入陣列外只使用常數額外空間。

Code

def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    def check(mid: int) -> bool:
        left_k = k
        for i, x in enumerate(A, start=1):
            if x >= mid:
                continue
            # 使用 math.ceil 會有浮點數誤差
            # left_k -= math.ceil((mid - x) / i)
            left_k -= ((mid - x) + i - 1) // i
            if left_k < 0:
                return False
        return True

    left = min(A)
    right = min(x + i * k for i, x in enumerate(A, start=1))
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            left = mid + 1
        else:
            right = mid - 1
    print(right)


if __name__ == "__main__":
    solve()