Overview

Given \(N\) laptops, select the one with the maximum cost performance \(\frac{S_i}{R_i}\) and output its number.

Analysis

This problem requires calculating the performance score \(S_i\) divided by the price \(R_i\) for each laptop, i.e., \(\frac{S_i}{R_i}\), and finding the laptop number with the highest value.

A straightforward approach is to compute the cost performance for all laptops and compare them while keeping track of the maximum value. This may appear efficient at first glance, but since the constraint is as large as \(N \leq 2 \times 10^5\), using an incorrect comparison method (such as comparing all pairs) could result in TLE (Time Limit Exceeded). However, since it suffices to examine each element exactly once, we can solve this in linear time.

Additionally, note that if multiple laptops have the same cost performance, we must select the one with the smallest number. This is naturally satisfied by iterating from the beginning in order and updating only when a value is strictly greater than the current maximum (i.e., not updating when the values are equal).

Algorithm

1. Read the information for each laptop in order and compute the cost performance \(\frac{S_i}{R_i}\).
2. If the value is higher than the current maximum cost performance, update the maximum value and the index.
3. Output the index recorded at the end.

Here, by initializing the maximum cost performance to a very small value (e.g., \(-1\)), we ensure that the first laptop is always selected.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Since we only scan each laptop once to find the answer, the time complexity is \(O(N)\). Also, since we only maintain a constant number of variables, the space complexity is \(O(1)\).

Implementation Notes

• Compute cost performance using floating-point arithmetic (in Python, the regular / operator works fine)

• By using > as the update condition for the maximum, ties are broken in favor of the smaller number

• Indices are 0-based, but the output is 1-based, so they need to be recorded as i+1

  Source Code

N = int(input())
max_performance = -1
best_index = -1

for i in range(N):
    R, S = map(int, input().split())
    performance = S / R
    if performance > max_performance:
        max_performance = performance
        best_index = i + 1

print(best_index)

This editorial was generated by qwen3-coder-480b.