B - Dreamoon's Criterion

題目大意

夢月解題目會根據夢月法則？如果題目需要花費大於 $t$ 的時間，則定義題目難度為 hard，反之為 easy。大頭蕃 準備 $n$ 個題目請求夢月協助，但隨著每解一題，下一題的難度會隨著疲累值增加，疲累值為一個等差為 $k$ 個數列。只打算解決 easy 的題目，請問在相同的 $k$ 下，不同的 $t$ 分別能解決的最多題數。

感謝 morris 提供題目大意！

題解

觀察一

只要 $t$ 越大，能解的題目就會越多。

觀察二

假設 $t, k$ 固定。若存在一個順序可以解決 $L$ 題，那麼一定有一組解，僅包含所需時間最少的 $L$ 題。

解法

由觀察一、二，假設 $a[0], a[1], \cdots, a[n]$ 是由小到大排好序的。我們可以知道：若對於一個 $t$，我們可以解決 $L$ 題，那麼必定有

$\max( a[0]+(L-1)\times k, a[1]+(L-2)\times k, \cdots, a[L-1] ) \le t$

我們把不等式左邊定義成 $b[L]$，於是有 $b[L] = \max(b[L-1] + k, a[L])$，我們可以花 $O(n)$ 的時間求出陣列 $b$。對於每一個 $t$ 我們可以進行二分搜尋法找出滿足條件的最大 $L$。