Overview

Compare the cost performance \(\frac{S_i}{R_i}\) of each laptop PC and find the number of the PC with the maximum value (if there is a tie, choose the smallest number).

Analysis

If we just want to find the maximum \(\frac{S_i}{R_i}\), it seems like we could simply compute the value for each PC and take the maximum. However, if we naively divide using floating point (float) and compare, rounding errors may cause values that should be equal to appear different, or reverse the magnitude relationship, leading to WA.

Therefore, we compare fractions without division by using cross multiplication. For two PCs \(a, b\): - To check whether \(\frac{S_a}{R_a} > \frac{S_b}{R_b}\), - We can determine this by checking \(S_a \cdot R_b > S_b \cdot R_a\)

(Since \(R_a, R_b > 0\), the direction of the inequality does not change.)

This allows exact comparison using only integer arithmetic, and a single scan is more than sufficient even for \(N \le 2 \times 10^5\).

In the case of a tie (\(\frac{S_a}{R_a} = \frac{S_b}{R_b}\)), we need to select “the one with the smaller number.” By keeping the one found first, we simply don’t update when values are equal, which satisfies the condition.

Algorithm

1. Record the 1st PC as the “tentative best” (best_R, best_S, best_idx).
2. Read each PC \((R, S)\) in order from \(i = 2\) to \(N\).
3. Compare the current PC with the tentative best using cross multiplication:
   • left = S * best_R
   • right = best_S * R
   • If left > right, then \(\frac{S}{R} > \frac{best\_S}{best\_R}\), so update the tentative best to this PC.
   • If left == right (tie), do not update (because the smaller number is already retained).
4. Output best_idx at the end.

Example: If the best is \((R, S) = (10, 6)\) (\(\frac{6}{10}\)) and the next is \((15, 10)\) (\(\frac{10}{15}\)), then we compare \(10 \cdot 10 = 100\) with \(6 \cdot 15 = 90\), and since \(100 > 90\), the next one has better cost performance.

Complexity

• Time complexity: \(O(N)\) (each PC is compared once)
• Space complexity: \(O(1)\) (only the best information is stored)

Implementation Notes

• Do not compare using division (floating point); always compare using cross multiplication \(S_1 R_2\) and \(S_2 R_1\).

• To prioritize the “smallest number” in case of a tie, only update when >, and do not update when ==.

• Since the input can be up to \(2 \times 10^5\) lines, using sys.stdin.readline ensures stable and fast performance.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    best_idx = 1
    best_R, best_S = map(int, input().split())

    for i in range(2, N + 1):
        R, S = map(int, input().split())
        left = S * best_R
        right = best_S * R
        if left > right:
            best_idx = i
            best_R, best_S = R, S
        # if equal, keep earlier index (already best)

    print(best_idx)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.