概要

各機械の作業時間 \(T_i\) は必ず全て足され、工具整備時間 \(R_i\) は「最後に作業した機械」だけ不要になります。したがって「最後に回す機械をどう選ぶか」だけを考えれば最短時間が求まります。

考察

機械をある順番でメンテナンスすると、時間の流れは

• 機械の作業：\(T\)
• （最後以外）工具整備：\(R\)
• 次の機械へ…

となります。

ここで重要なのは次の2点です。

1. 全ての \(T_i\) は順番に関係なく必ず合計される
   どの順番でも、全機械を1回ずつ作業するので合計作業時間は常に \(\\sum T_i\) です。

2. \(R_i\) は「最後に作業した機械」だけ発生しない
   最後の機械の後には次の作業が無いので工具整備が不要です。
   つまり、発生する工具整備時間の合計は
   [ \sum Ri - R{\text{last}} ] となります（\(R_{\text{last}}\) は最後に選んだ機械の \(R\)）。

よって、総時間は [ \sum T_i + \left(\sum Ri - R{\text{last}}\right) ] です。これを最小にするには、引かれる値 \(R_{\text{last}}\) を最大にすればよいので、最後に回す機械は \(R_i\) が最大のものが最適です。

素朴に全ての順番（\(N!\) 通り）を試すのは \(N \le 2\times 10^5\) では不可能です。しかし上の観察により、順番全体を考える必要はなく「最大の \(R_i\) を最後にする」だけで解けます。

例：\((T,R)=(3,5),(10,2),(4,7)\) のとき
[ \sum T=17,\ \sum R=14,\ \max R=7 ] 最短時間は [ 17+14-7=24 ] （\(R=7\) の機械を最後にすればよい）。

アルゴリズム

1. \(\\text{sum\_t} = \sum T_i\) を計算する
2. \(\\text{sum\_r} = \sum R_i\) を計算する
3. \(\\text{max\_r} = \max R_i\) を求める
4. 答えを [ \text{sum_t} + \text{sum_r} - \text{max_r} ] として出力する

計算量

• 時間計算量: \(O(N)\)（1回の走査で合計と最大を取るだけ）
• 空間計算量: \(O(1)\)（入力を保持せず集計値のみ）

実装のポイント

• \(T_i, R_i\) は最大 \(10^9\)、\(N\) は最大 \(2\times 10^5\) なので、合計は最大で約 \(2\times 10^{14}\) になります。Python の int なら安全ですが、他言語では 64bit 整数を使います。

• 全データを配列に保存する必要はなく、読みながら sum_t, sum_r, max_r を更新すれば十分です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    sum_t = 0
    sum_r = 0
    max_r = 0
    for _ in range(N):
        t, r = map(int, input().split())
        sum_t += t
        sum_r += r
        if r > max_r:
            max_r = r
    print(sum_t + sum_r - max_r)

if __name__ == "__main__":
    main()

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