概要

各スタッフの割り当て \(X_i\) を上限 \(R_i\) 以内で合計 \(M\) にしつつ、\(\max(R_i - X_i)\)（上限との差の最大）を最小化する問題です。
「不足分」をうまく配る問題に言い換え、二分探索で最小の不公平度を求めます。

考察

1. 「割り当て」ではなく「不足分」を考える

不公平度は \(R_i - X_i\) の最大値です。そこで - 不足分 \(D_i = R_i - X_i\)（\(0 \le D_i \le R_i\)） と置くと、条件 \(X_1+\cdots+X_N=M\) は次のように変形できます。

\(S=\sum_{i=1}^N R_i\) とすると
[ \sum_{i=1}^N Xi = \sum{i=1}^N (R_i - Di) = S - \sum{i=1}^N Di = M ] よって [ \sum{i=1}^N D_i = S - M = T ] となります。

つまり問題は、

• 各 \(D_i\) は \(0 \le D_i \le R_i\)
• 合計 \(\sum D_i = T\)
• 最大値 \(\max D_i\) を最小化

に言い換えられます。

また、もし \(M > S\) なら、全員を上限まで入れても \(M\) コマに届かないので不可能 → -1 です。

2. 素朴に最適な割り当てを作ろうとすると難しい

「不公平度を最小にするように \(X_i\) を直接構成する」ことを考えると、調整が複雑で \(N\) が最大 \(2\times 10^5\)、値も最大 \(10^{18}\) と大きいため、愚直な探索やシミュレーションは現実的ではありません。

3. 「不公平度 \(d\) が可能か？」は単調になる

不公平度の候補 \(d\)（つまり \(\max D_i \le d\)）を固定して、「合計不足分 \(T\) を作れるか？」を判定します。

各スタッフ \(i\) の不足分は最大でも \(\min(d, R_i)\) までしか増やせません。よって、作れる不足分の合計の最大は [ C(d) = \sum_{i=1}^N \min(d, R_i) ] です。

• \(C(d) \ge T\) なら、各 \(D_i\) を調整して合計 \(T\) を作れる（不足分を減らす方向は常に可能なので）→ 可能
• \(C(d) < T\) なら、どう頑張っても合計 \(T\) に届かない → 不可能

そして \(d\) を大きくすると \(\min(d, R_i)\) は増える（または据え置き）ので、\(C(d)\) は 単調増加。
よって「可能/不可能」は \(d\) に関して単調になり、二分探索が使えます。

具体例

\(R=[5,1,4],\ M=7\) のとき、\(S=10,\ T=S-M=3\)。
\(d=1\) なら \(C(1)=1+1+1=3\) なので可能（不公平度 1 で不足分合計 3 を作れる）。
\(d=0\) なら \(C(0)=0\) で不可能。よって答えは 1 です。

アルゴリズム

1. \(S=\sum R_i\) を計算する。
2. \(M > S\) なら -1 を出力して終了。
3. \(T = S - M\) を計算する。
   • \(T=0\)（つまり \(M=S\)）なら不足分は不要なので不公平度は \(0\)。
4. 二分探索で最小の \(d\) を求める。
   • 探索範囲：\(0 \le d \le \max R_i\)
   • 判定関数：\(C(d)=\sum \min(d, R_i)\) を計算し、\(C(d)\ge T\) なら可能
5. 求まった最小の \(d\) を出力。

コードでは二分探索を - lo = 不可能な値 - hi = 可能な値
として lo=-1, hi=maxR から始め、hi を答えにしています。

計算量

• 時間計算量: \(O(N \log(\max R_i))\)
  （各判定が \(O(N)\)、二分探索が最大で約 60 回程度）
• 空間計算量: \(O(N)\)
  （配列 \(R\) を保持）

実装のポイント

• 不可能判定：\(M > \sum R_i\) のときは必ず -1。

• \(T=0\) の特別処理：不足分ゼロなので答えは必ず \(0\)。

• 二分探索の上限は \(\max R_i\) で十分（それ以上にしても \(\min(d,R_i)\) は変わらない）。

• 判定計算 \(\sum \min(d,R_i)\) は、途中で合計が \(T\) 以上になったら打ち切ると高速です（コードの break）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    R = data[2:2+N]

    S = 0
    maxR = 0
    for r in R:
        S += r
        if r > maxR:
            maxR = r

    if M > S:
        print(-1)
        return

    T = S - M  # total deficit needed
    if T == 0:
        print(0)
        return

    lo, hi = -1, maxR  # lo: infeasible, hi: feasible
    while hi - lo > 1:
        mid = (lo + hi) // 2
        c = 0
        for r in R:
            c += mid if mid < r else r
            if c >= T:
                break
        if c >= T:
            hi = mid
        else:
            lo = mid

    print(hi)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。