問題説明

モンドの街の冒険者たちは、風神祭を祝うため特別なパフォーマンスを計画しています。このパフォーマンスには「冒険者の塔」という特殊な挑戦が含まれており、これは冒険者たちのチームワークと個人の耐久力を試す活動です。

「冒険者の塔」パフォーマンスでは、参加者は互いの肩の上に立ち、人間の塔を形成し、その勇気とチーム精神を示す必要があります。各冒険者にはそれぞれ重量と耐久力（負荷がかかりすぎて怪我をしない限界値）があります。パフォーマンスの安全性を確保するため、主催者は、塔の中のどの冒険者も経験する限界値（つまり、頭上の全員の総重量からその人の耐久力を引いた値）を可能な限り小さくするような参加者の順序付けを計算する必要があります。

最大限界値を最小にするような解法を見つけてください。

入力

最初の行には整数Nが入力され、これは冒険者の数を表します。

次のN行には、各冒険者の重量Wiと耐久力Siを表す2つの整数が入力されます。

1≤N≤50000, 1≤Wi≤10,000, 1≤Si≤1,000,000,000

出力

整数を出力し、それは最小化された最大限界値を表します。

入力例1

3
10 3
2 5
3 3

出力例1

2

解法：

この問題は古典的な貪欲アルゴリズムのテンプレート問題です。

i+1番目の人がi番目の人の下にいる場合、各人の負荷は次のように計算されます。

Vi = W(1i-1) - si Vi+1 = W(1i) - si+1

両者の位置を交換すると、

Vi = W(1i-1) - si + Wi+1 Vi+1 = W(1i-1) - si+1

最適性を考慮すると、交換すべきかどうかは次の条件に依存します：

W(1i-1) - si + Wi+1 < W(1i) - si+1 つまり、-si + Wi+1 < Wi - si+1 → Wi+1 + si+1 < Wi + si

この条件が満たされる場合、両者の位置を交換する必要があります。したがって、シーケンスをw + sの昇順でソートするだけで十分です。

コード実装：

import sys

def solve():
    # 入力データの読み込み
    data = sys.stdin.read().split()
    n = int(data[0])
    adventurers = []
    index = 1
    total_weight = 0
    
    # 冒険者のデータをリストに格納
    for _ in range(n):
        weight = int(data[index])
        strength = int(data[index + 1])
        index += 2
        adventurers.append((weight + strength, weight, strength))
    
    # 冒険者をweight + strengthの昇順でソート
    adventurers.sort()
    
    max_stress = -float('inf')
    cumulative_weight = 0
    
    # 各冒険者の負荷を計算
    for _, weight, strength in adventurers:
        # 現在の冒険者の負荷を計算
        current_stress = cumulative_weight - strength
        # 最大負荷を更新
        if current_stress > max_stress:
            max_stress = current_stress
        # 累積重量を更新
        cumulative_weight += weight
    
    # 結果を出力
    print(max_stress)

if __name__ == "__main__":
    solve()

注意点として、最初はmapコンテナを使用していました（キー値による自動ソート機能があるためですが）、一部のテストケースにパスできませんでした。これはmapコンテナの内部実装に関連しており、mapは木構造であり、キー値が等しい場合の処理ができません。つまり、キー値が等しい場合、mapコンテナのソートはランダムになります。私たちが必要としているのは、キー値が等しい場合には、耐久力が大きい人が下にくるようにソートすることです。