Best Broadcast Budget

$N$ 人目の参加者の競技は必ず放送しなければなりません。

そこで、まず $N$ 人目の競技時間である $A_N$ 秒を確保します。残りの $T-A_N$ 秒を使って、$1,2,\ldots,N-1$ 人目からできるだけ多くの参加者を選ぶことを考えます。

放送する人数を増やすためには、競技時間が短い参加者から選ぶのが最適です。

$A_1,A_2,\ldots,A_{N-1}$ を昇順に並べた列を $C = (C_1 , C_2 , \cdots , C_{N-1})$ とします。

最初の $N-1$ 人から $k$ 人を選ぶとき、その競技時間の合計として最小になるのは、競技時間が短い方から $k$ 人を選んだ場合です。

その合計は $C_1+C_2+\cdots+C_k$ 秒です。

したがって、

$$A_N+C_1+C_2+\cdots+C_k \leq T$$

が成り立つなら、$N$ 人目を含めて $k+1$ 人を放送できます。

一方、この不等式が成り立たないなら、最初の $N-1$ 人からどのように $k$ 人を選んでも、競技時間の合計は $T$ を超えてしまいます。

よって、次のように処理すればよいです。

$A_1,A_2,\ldots,A_{N-1}$ を昇順に並べる。 $N$ 人目を放送することにして、競技時間の合計を $A_N$、人数を $1$ とする。 競技時間が短い参加者から順に、追加しても合計が $T$ 以下なら放送する。 追加できなくなった時点での人数を出力する。

列は昇順に並んでいるため、ある参加者を追加できなかった場合、それ以降の参加者も追加できません。

$A_1,A_2,\ldots,A_{N-1}$ のソートに $O(N\log N)$、その後の走査に $O(N)$ かかります。

したがって、全体の計算量は $O(N\log N)$ です。