概要

\(N\) 個のノートPCから、コストパフォーマンス \(\frac{S_i}{R_i}\) が最大となるものを選び、その番号を出力する問題。

考察

この問題は、各ノートPCの性能スコア \(S_i\) を価格 \(R_i\) で割った値、つまり \(\frac{S_i}{R_i}\) を計算し、その値が最も大きくなるノートPCの番号を求めることになります。

素朴な方法としては、すべてのノートPCについてコストパフォーマンスを計算し、最大値を記録しながら比較していくことが考えられます。これは一見効率的に見えますが、制約が \(N \leq 2 \times 10^5\) と大きいため、もし誤った比較方法（たとえば全ペア比較など）をとるとTLE（時間超過）してしまう可能性があります。しかし、今回は各要素を1回ずつ見れば十分なので、線形時間で解くことができます。

さらに、同じコストパフォーマンスを持つノートPCが複数ある場合、番号が最も小さいものを選ぶ必要がある点に注意が必要です。これは単純に最初から順番に見て行って、今持っている最大値より strict に大きい場合にのみ更新すれば自然に満たされます（同じ値のときは更新しない）。

アルゴリズム

1. 各ノートPCの情報を順番に読み込みながら、コストパフォーマンス \(\frac{S_i}{R_i}\) を計算する。
2. 現在の最大コストパフォーマンスよりも高い値であれば、その値とインデックスを更新する。
3. 最後に記録されたインデックスを出力する。

このとき、初期値として最大コストパフォーマンスを非常に小さな値（例えば \(-1\)）にしておくことで、最初のノートPCが必ず選ばれるようにします。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

各ノートPCを一度だけ走査するだけで答えが求められるため、時間計算量は \(O(N)\) です。また、保持する変数は定数個しかないため、空間計算量は \(O(1)\) となります。

実装のポイント

• コストパフォーマンスを浮動小数点数型で計算すること（Pythonでは普通の / 演算子でOK）

• 最大値の更新条件を > とすることで、同率の場合に番号が小さい方を優先できる

• インデックスは0始まりだが、出力は1始まりなので、i+1として記録する必要がある

  ソースコード

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)

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