AtCoder 🟠 ABC437C Reindeer and Sleigh 2

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC437C Reindeer and Sleigh 2

rating: 546

Problem Statement

題意簡述

有 $N$ 隻馴鹿，第 $i$ 隻馴鹿的體重為 $W_i$，力量為 $P_i$。
每隻馴鹿可以選擇「拉雪橇」或「坐雪橇」。

限制條件：拉雪橇的馴鹿的總力量必須大於等於坐雪橇的馴鹿的總體重。

請問最多可以有多少隻馴鹿坐雪橇？

Constraints

約束條件

• $1\leq N\leq 3\times 10^5$
• $1\leq W_i,P_i\leq 10^9$

---

思路：不等式轉換 + 貪心 (Greedy)

這道題目要求我們將 $N$ 隻馴鹿分為兩組：拉雪橇的集合 $S$ 和坐雪橇的集合 $R$。
目標是最大化坐雪橇的數量 $|R|$，且滿足條件：

$$\sum_{i \in S} P_i \ge \sum_{j \in R} W_j$$

由於每隻馴鹿非此即彼，即 $S \cup R = \{1, 2, \dots, N\}$ 且 $S \cap R = \emptyset$，我們可以利用總力量 $\sum_{k=1}^N P_k$ 來進行代換。
拉雪橇的總力量可以表示為「全體總力量」減去「坐雪橇者的力量」：

$$\sum_{i \in S} P_i = \sum_{k=1}^N P_k - \sum_{j \in R} P_j$$

將此式代回原限制條件：

$$\sum_{k=1}^N P_k - \sum_{j \in R} P_j \ge \sum_{j \in R} W_j$$

移項整理後得到：

$$\sum_{k=1}^N P_k \ge \sum_{j \in R} W_j + \sum_{j \in R} P_j$$

$$\sum_{k=1}^N P_k \ge \sum_{j \in R} (W_j + P_j)$$

貪心策略

觀察轉換後的不等式：

• 左邊 $\sum_{k=1}^N P_k$ 是一個定值（所有馴鹿的力量總和）。我們可以將其視為初始的「預算」。
• 右邊是所有坐雪橇馴鹿的 $(W_j + P_j)$ 總和。我們可以將 $W_j + P_j$ 視為讓第 $j$ 隻馴鹿坐雪橇的「花費」。

為了讓更多馴鹿坐雪橇（最大化 $|R|$），我們應該優先選擇「花費」最小的馴鹿。
因此，解題步驟如下：

1. 計算所有馴鹿的力量總和作為初始預算。
2. 計算每隻馴鹿的代價 $C_i = W_i + P_i$。
3. 將馴鹿按照 $C_i$ 由小到大排序。
4. 依序選取馴鹿進入集合 $R$，並從預算中扣除其代價，直到預算不足以支付下一隻馴鹿的代價為止。

為什麼這是正確的？

由於我們只關心「數量」，而不關心具體是誰，所以在預算有限的情況下，每次選最便宜的必定能選到最多個。

複雜度分析

• 時間複雜度：主要消耗在排序上，為 $\mathcal{O}(N \log N)$。
• 空間複雜度：儲存馴鹿資料，為 $\mathcal{O}(N)$。

---

Code

def solve():
    n = int(input())
    A = [tuple(map(int, input().split())) for _ in range(n)]

    A.sort(key=lambda x: x[0] + x[1])
    s = sum(p for w, p in A)
    
    ans = 0
    for w, p in A:
        s -= (w + p)
        if s < 0:
            break
        ans += 1
    print(ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()