概要

各部屋の温度を同じ整数 \(T\) にそろえるときのコスト最小化問題です。
目的関数 \(\sum S_i|P_i-T|\) は「重み付き絶対値和」なので、最適な \(T\) は 重み付き中央値 になります。

考察

この問題は、次の式を最小化する \(T\)（整数）を探す問題です。

\[ f(T)=\sum_{i=1}^{N} S_i \times |P_i-T| \]

重要な気づき

重みなしの \(\sum |P_i-T|\) を最小化する \(T\) が中央値になるのと同様に、
重み \(S_i\) がある場合は 重み付き中央値 が最適です。

• 温度を小さい順に並べる
• 重み（ここでは広さ）を左から累積する
• 累積重みが全体の半分以上になる最初の温度が重み付き中央値

この点を \(T\) にすると、左右どちらへ 1 動かしてもコストは下がりません。

素朴解が厳しい理由

例えば、\(T\) を \(-10^9\) から \(10^9\) まで全部試すと候補数が多すぎて不可能です。
各候補で全室を走査するとさらに \(O(N)\) かかるため、完全に TLE になります。

どう解決するか

温度をソートして重み付き中央値を 1 回で求め、最後にその \(T\) で総コストを計算します。
これなら主要コストはソートの \(O(N\log N)\) だけです。

アルゴリズム

1. 入力 \((S_i,P_i)\) を \((P_i,S_i)\) として配列に保存し、総重み \(W=\sum S_i\) を計算。
2. 温度 \(P_i\) の昇順にソート。
3. \(half=\left\lfloor\frac{W+1}{2}\right\rfloor\) を用意（「半分以上」の閾値）。
4. 左から累積重み acc を足していき、acc >= half になった最初の温度を \(T\) とする。
5. 答えを \(\sum S_i|P_i-T|\) で計算して出力。

この手順が提示コードそのものです。

計算量

• 時間計算量: \(O(N\log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（部屋情報の保持）

実装のポイント

• 重み付き中央値の閾値を half = (total_weight + 1) // 2 とすると、「半分以上」を整数で安全に扱えます。

• コストは大きくなる可能性がありますが、Python の整数は多倍長なのでオーバーフローの心配はありません。

• 入力が大きいため sys.stdin.readline を使うと高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    rooms = []
    total_weight = 0

    for _ in range(N):
        s, p = map(int, input().split())
        rooms.append((p, s))
        total_weight += s

    # Weighted median of temperatures
    rooms.sort()  # sort by temperature p
    half = (total_weight + 1) // 2
    acc = 0
    T = rooms[0][0]
    for p, s in rooms:
        acc += s
        if acc >= half:
            T = p
            break

    # Compute minimum cost at weighted median
    ans = 0
    for p, s in rooms:
        ans += s * abs(p - T)

    print(ans)

if __name__ == "__main__":
    main()

---

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