概要

\(N\) 台の機械を適切な順番でメンテナンスし、最後の機械のメンテナンスが完了するまでの最短時間を求める問題です。

考察

この問題では、各機械のメンテナンス時間 \(T_i\) とその後の工具整備時間 \(R_i\) が与えられます。
ただし、最後の機械をメンテナンスした後は工具整備が不要であるという点が重要です。

素朴なアプローチとして、全順列を試す方法（bit全探索やnext_permutationなど）が考えられますが、\(N\) が最大 \(2 \times 10^5\) なので、これは計算量的に不可能です（\(O(N!)\) は非常に大きい）。

では、どうやって効率よく最適な順番を求めればよいでしょうか？

ここで重要な観察があります：
最後以外の機械については、工具整備時間 \(R_i\) が小さい順にメンテナンスを行うのが最適です。

理由を考えてみましょう。
例えば、ある2つの機械 A\((T_A, R_A)\) と B\((T_B, R_B)\) をこの順で行う場合、合計時間は： $\( (T_A + R_A) + (T_B) = T_A + R_A + T_B \)\( 逆に B→A の順なら： \)\( (T_B + R_B) + (T_A) = T_B + R_B + T_A \)\( どちらが早いのかは、\)R_A\( と \)R_B$ の大小関係によります。
つまり、工具整備時間が小さい方を先に行うと全体が短くなるのです。

また、最後の1台だけは工具整備が不要なので、最後に工具整備時間が最も大きいものを持ってきたいところです。

したがって、\((R_i, T_i)\) のペアを \(R_i\) の昇順にソートし、その順にメンテナンスすれば最短時間となることがわかります。

アルゴリズム

1. 各機械について \((T_i, R_i)\) を読み込む。
2. \((R_i, T_i)\) のペアでリストを作り、\(R_i\) の昇順にソートする（同じ \(R_i\) の場合は \(T_i\) の昇順でもよい）。
3. ソートされた順に機械をメンテナンスしていく。
   • 各機械に対して、\(T_i\) を加算する。
   • 最後の機械でなければさらに \(R_i\) を加算する。
4. 合計時間を出力する。

例

入力例：

3
3 2
1 4
2 1

\((T_i, R_i)\): (3,2), (1,4), (2,1)
\((R_i, T_i)\) でソート: (1,2), (2,3), (4,1) → 順に機械3, 1, 2 をメンテナンス

時系列： - 機械3: 作業時間2秒 → 終了時刻2、整備時間1秒（合計3秒） - 機械1: 作業時間3秒 → 終了時刻6、整備時間2秒（合計8秒） - 機械2: 作業時間1秒 → 終了時刻9（整備不要）

答えは 9 秒。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(N)\) （入力を格納する配列）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使う。
• ペアをソートする際、キーを (R_i, T_i) とすることで、工具整備時間が同じ場合も安定した結果を得られる。
• 最後の機械には工具整備時間を加算しないことに注意。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    TR = [(int(data[2*i+1]), int(data[2*i+2])) for i in range(N)]
    
    # 各機械の (T_i, R_i) を扱う
    # 最後に工具整備は不要なので、最後の機械は R_i が大きい順にしたくない
    # つまり、最後以外は R_i の小さい順に並べるのが最適
    
    # (R_i, T_i) でソートして、R_i の小さい順に並べる
    TR.sort(key=lambda x: (x[1], x[0]))
    
    total = 0
    for i in range(N):
        T, R = TR[i]
        total += T
        if i != N - 1:
            total += R
            
    print(total)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。