Overview

Given \(N\) rooms, the problem asks to unify all room temperatures to a single integer value \(T\) while minimizing the weighted sum of absolute deviations \(\sum S_i \times |P_i - T|\). This can be solved by finding the weighted median.

Analysis

Key Insight: The Weighted Median is Optimal

First, consider the case where all weights are \(1\). It is well known that the \(T\) minimizing \(\sum |P_i - T|\) is the median of the \(P_i\) values.

In this problem, each room has a weight given by its area \(S_i\). Intuitively, a room \(i\) with area \(S_i\) can be interpreted as “\(S_i\) rooms each at temperature \(P_i\).” In this case, the optimal \(T\) is the weighted median.

Why a Naive Approach Fails

Since \(P_i\) ranges from \(-10^9\) to \(10^9\), trying all integers \(T\) would require checking \(O(2 \times 10^9)\) candidates, which is far too slow.

How to Solve It

The optimal \(T\) must equal one of the \(P_i\) values (because the weighted sum of absolute deviations is a piecewise linear function with breakpoints at the \(P_i\) positions). Furthermore, using the properties of the weighted median, we can narrow down the candidates to a single value.

Algorithm

1. Sort: Sort the rooms in ascending order of temperature \(P_i\).
2. Find the Weighted Median: Compute the total weight \(W = \sum S_i\), then accumulate the weights \(S_i\) in sorted order. The temperature \(P_i\) at the first position where the cumulative weight reaches at least \(W / 2\) is the weighted median.
3. Compute the Cost: Calculate the cost at the weighted median and its neighbors (\(T-1, T, T+1\)), then output the minimum.

Concrete Example

For 3 rooms with \((S, P) = (3, 10), (1, 20), (2, 30)\):

• Sort by \(P\) in ascending order → \((3,10), (1,20), (2,30)\)
• Total weight \(W = 3 + 1 + 2 = 6\)
• Cumulative weights: \(3 \to 4 \to 6\). The first time it reaches \(\geq 6/2 = 3\) is at cumulative weight \(3\) → \(T = 10\)
• Cost: \(3 \times |10-10| + 1 \times |20-10| + 2 \times |30-10| = 0 + 10 + 40 = 50\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting; the median search and cost computation are each \(O(N)\))
• Space complexity: \(O(N)\) (to store the room information)

Implementation Notes

• Weighted Median Condition: The median is the first position where cumulative weight \(\times 2 \geq\) total weight. This finds the smallest \(P_i\) such that the total weight on its left side (inclusive) is at least half of the overall weight.

• Check Neighboring Candidates: To guard against subtle off-by-one issues due to integer constraints and boundary conditions, we also try \(T \pm 1\) as candidates for safety. However, theoretically the weighted median itself is optimal.

• Fast Input: Using sys.stdin.buffer.read() to read all input at once allows efficient processing even when \(N\) is large.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    rooms = []
    for i in range(N):
        s = int(input_data[idx]); idx += 1
        p = int(input_data[idx]); idx += 1
        rooms.append((p, s))
    
    # Sort by temperature
    rooms.sort()
    
    # The optimal T is the weighted median of P_i with weights S_i
    # For weighted median: find the smallest P such that cumulative weight >= total_weight / 2
    
    total_weight = sum(s for _, s in rooms)
    
    # Find weighted median
    cumsum = 0
    median_idx = 0
    for i, (p, s) in enumerate(rooms):
        cumsum += s
        if cumsum * 2 >= total_weight:
            median_idx = i
            break
    
    # The optimal T is at or near rooms[median_idx][0]
    # Since T must be integer and P_i are integers, the weighted median P value works
    # But let's check the candidate and neighbors to be safe
    
    T_candidate = rooms[median_idx][0]
    
    def compute_cost(T):
        return sum(s * abs(p - T) for p, s in rooms)
    
    best = compute_cost(T_candidate)
    for delta in [-1, 0, 1]:
        cost = compute_cost(T_candidate + delta)
        if cost < best:
            best = cost
    
    print(best)

solve()

---

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