Overview

This is a problem where you maintain \(N\) machines in any order you choose, and you want to minimize the total of working time and tool preparation time. The key point is that tool preparation is not needed after the last machine.

Analysis

Understanding the Structure of Total Time

When maintaining machines in some order \(\sigma_1, \sigma_2, \dots, \sigma_N\), the total time is:

\[\text{Total time} = \underbrace{T_{\sigma_1} + R_{\sigma_1}}_{\text{1st machine}} + \underbrace{T_{\sigma_2} + R_{\sigma_2}}_{\text{2nd machine}} + \cdots + \underbrace{T_{\sigma_{N-1}} + R_{\sigma_{N-1}}}_{\text{(N-1)-th machine}} + \underbrace{T_{\sigma_N}}_{\text{Last (no preparation needed)}}\]

Rearranging this:

\[\text{Total time} = \sum_{i=1}^{N} T_i + \sum_{i=1}^{N} R_i - R_{\sigma_N}\]

Here is the crucial observation: \(\sum T_i\) and \(\sum R_i\) are constant regardless of the order. The only thing that changes is \(R_{\sigma_N}\), the tool preparation time of the last machine to be maintained.

Optimal Strategy

Since the total time is \(\sum T_i + \sum R_i - R_{\sigma_N}\), to minimize this we need to maximize \(R_{\sigma_N}\).

In other words, it is optimal to maintain the machine with the largest tool preparation time \(R_i\) last.

Concrete Example

For example, with \(N = 3\) and \((T_1, R_1) = (2, 5)\), \((T_2, R_2) = (3, 1)\), \((T_3, R_3) = (4, 3)\):

• \(\sum T_i = 2 + 3 + 4 = 9\)
• \(\sum R_i = 5 + 1 + 3 = 9\)
• \(\max(R_i) = 5\) (machine 1)

By placing machine 1 last, the total time \(= 9 + 9 - 5 = 13\) seconds, which is the minimum.

Algorithm

1. Compute the sum of all \(T_i\): \(\sum T_i\).
2. Compute the sum of all \(R_i\): \(\sum R_i\).
3. Find the maximum value of \(R_i\): \(\max(R_i)\).
4. The answer is \(\sum T_i + \sum R_i - \max(R_i)\).

Complexity

• Time complexity: \(O(N)\) — just a single pass through all values
• Space complexity: \(O(N)\) — used for storing the input (can be reduced to \(O(1)\) if only running totals are kept)

Implementation Notes

• Since \(T_i, R_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total can be approximately \(4 \times 10^{14}\). In Python there is no need to worry about integer overflow, but in C++ and similar languages you need to use long long.

• There is no need to actually construct the ordering; computing just the sums and the maximum is sufficient.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    machines = []
    for i in range(N):
        T = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        machines.append((T, R))
    
    # Total time = sum of all T_i + sum of R_i for all except the last machine
    # We want to minimize total time, so we want to maximize the R of the last machine
    # But wait - we need to think more carefully.
    #
    # Total time = sum(T_i) + sum of R_i for machines not last
    # = sum(T_i) + sum(R_i) - R_last
    # To minimize, we maximize R_last, i.e., put the machine with largest R last.
    
    total_T = sum(t for t, r in machines)
    total_R = sum(r for t, r in machines)
    max_R = max(r for t, r in machines)
    
    print(total_T + total_R - max_R)

main()

---

This editorial was generated by claude4.6opus-thinking.