Overview

This problem asks us to unify the room temperatures of \(N\) rooms to some integer \(T\), minimizing the total weighted absolute error \(\sum S_i |P_i - T|\), where \(S_i\) is the size (weight) of each room. This reduces to finding the weighted median in statistics.

Analysis

1. Properties of the Objective Function

Consider the function we want to minimize: \(f(T) = \sum_{i=1}^{N} S_i |P_i - T|\). If all \(S_i\) were \(1\), it is well known that the \(T\) minimizing this function is the median of the \(P_i\) values. In this problem, each \(P_i\) has a weight \(S_i\), so we need to find the weighted median.

2. Why the Median?

The function \(f(T)\) is a convex function (convex downward graph), and its slope changes as follows when \(T\) increases: - When \(T\) is increased by \(1\), the cost for rooms with \(P_i\) smaller than the current \(T\) increases by \(S_i\) each, while the cost for rooms with \(P_i\) larger than the current \(T\) decreases by \(S_i\) each. - In other words, the minimum occurs at the point where the slope transitions from negative to positive (the point where the cumulative weight exceeds half of the total weight).

3. The Constraint that \(T\) Must Be an Integer

The problem states that “\(T\) must be an integer,” but all the breakpoints of the function (points where the slope changes) are located at the input values \(P_i\) (which are integers). Therefore, the weighted median \(P_k\) is always an integer and can be directly used as the optimal \(T\).

Algorithm

1. Obtain each room’s information as a pair of temperature \(P_i\) and size \(S_i\), and sort them in ascending order of temperature \(P_i\).
2. Compute the total size of all rooms \(W = \sum S_i\).
3. Accumulate the sizes \(S_i\) in sorted order, and set the target temperature \(T\) to the temperature \(P_k\) at the moment the cumulative sum reaches \(W/2\) or more.
4. Using the obtained \(T\), compute and output the total cost \(\sum S_i |P_i - T|\).

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the rooms takes \(O(N \log N)\). The subsequent cumulative sum computation and cost calculation each take \(O(N)\).
• Space Complexity: \(O(N)\)
  • Required to store the information of \(N\) rooms in a list.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(150,000\), in Python it is recommended to read all input at once using sys.stdin.read().split() to reduce execution time.

• Weighted Median Determination: If the cumulative sum is current_w, using the condition current_w * 2 >= total_w (clearing the denominator) allows accurate determination of “at least half” while avoiding floating-point errors.

• Handling Large Values: The final cost can become extremely large, but since Python natively supports arbitrary-precision integers, there is no need to worry about overflow.

  Source Code

import sys

def solve():
    # Fast I/O: read all input at once and split by whitespace
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        line = next(it)
    except StopIteration:
        return
    
    N = int(line)
    
    # The problem asks to minimize the function f(T) = sum(S_i * |P_i - T|)
    # where T is an integer. This is a weighted version of the median problem.
    # Since f(T) is a convex, piecewise linear function with corners at integer 
    # coordinates P_i, the minimum value will be achieved at one of the P_i.
    
    rooms = []
    # Each room has a size S_i and a temperature P_i
    for _ in range(N):
        try:
            s = int(next(it))
            p = int(next(it))
            rooms.append((p, s))
        except StopIteration:
            break
            
    # Sort the rooms by temperature P_i to find the weighted median
    # This operation is O(N log N)
    rooms.sort()
    
    # Calculate the total weight (sum of all sizes S_i)
    total_weight = sum(r[1] for r in rooms)
    
    # The weighted median target_t is the first temperature P_i where the 
    # cumulative weight reaches or exceeds half of the total weight.
    cumulative_weight = 0
    target_t = rooms[0][0]
    for p, s in rooms:
        cumulative_weight += s
        if cumulative_weight * 2 >= total_weight:
            target_t = p
            break
            
    # Calculate the minimum total cost using the found target_t
    # Total cost = sum(S_i * |P_i - target_t|)
    min_total_cost = 0
    for p, s in rooms:
        min_total_cost += s * abs(p - target_t)
        
    # Output the result as an integer
    sys.stdout.write(str(min_total_cost) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.