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

🔗 P4653 [CEOI 2017] Sure Bet

Problem Statement

題目簡述

有 $n$ 組燈泡，每組各有一顆 A 類與一顆 B 類燈泡，權值分別為 $A_i,B_i$ 。
你可以任意挑選一些燈泡，每挑一顆就要付出 $1$ 的代價。
最後系統會在 A 類與 B 類之間隨機選一種點亮，你只能拿到被點亮那一類、且你有挑選到的燈泡權值總和。

也就是說，若你挑了若干顆 A 與若干顆 B，最終保證收益為：

\min(\text{挑到的 A 權值總和},\ \text{挑到的 B 權值總和})-\text{挑選總顆數}

請最大化這個「最小可能收益」。

Constraints

約束條件

$0 \le n \le 10^5$
$1.0 \le A_i,B_i \le 1000.0$
輸入實數最多到小數點後四位
需輸出答案到小數點後恰好四位

思路：排序後只補較小的一側

1. 先把「怎麼挑」化成前綴問題

雖然輸入是成對給出 $(A_i,B_i)$ ，但題目並沒有要求同一組的兩顆燈泡必須一起選或一起不選。也就是說，A 類與 B 類的挑法其實彼此獨立，可以分開考慮。

假設我們最後決定：

從 A 類挑 $i$ 顆
從 B 類挑 $j$ 顆

那麼在這個前提下，最好的選法一定是：

A 類挑權值最大的前 $i$ 顆
B 類挑權值最大的前 $j$ 顆

理由很直接：既然挑選顆數已經固定，當然應該在各自類別中拿權值最高的那些燈泡，任何不是前幾大的選法都只會更差。

因此我們可以先把兩個陣列各自由大到小排序，並令：

$S_A(i)$ ：A 類前 $i$ 大的總和
$S_B(j)$ ：B 類前 $j$ 大的總和

此時若選的是這兩個前綴，保證收益就是：

f(i,j)=\min(S_A(i),S_B(j))-(i+j)

原題因此被改寫成一個更乾淨的目標：
在所有 $0 \le i,j \le n$ 中，最大化這個式子。

關鍵重寫

原題表面上像是在做組合選擇，但一旦固定了 A、B 各挑幾顆，最優集合就唯一地變成排序後的前綴，因此問題本質上只剩下狀態 $(i,j)$ 。

2. 為什麼只需要補目前較小的那一側？

假設目前在某個狀態 $(i,j)$ 。

若此時：

S_A(i) < S_B(j)

那麼當前的最壞情況就由 A 類決定，因為

f(i,j)=S_A(i)-i-j

這時如果不去補 A，而是再多拿一顆 B 類燈泡，會發生什麼？

$\min(S_A,S_B)$ 不會變大，因為較小者仍然是 $S_A(i)$
但代價會多 $1$

也就是說，答案只會變差，不可能變好。

所以當 $S_A(i) < S_B(j)$ 時，若還想讓答案上升，唯一可能有幫助的做法就是補 A 類下一顆；反過來，若 $S_A(i) > S_B(j)$ ，就只能補 B 類。

至於兩者剛好相等時，先補哪一邊都不影響正確性；。

核心貪心

目前較小的一側決定了最壞收益，因此只有補那一側，才有機會把 $\min(S_A,S_B)$ 往上推；補較大的一側只是在白白增加成本。

3. 何時可以停止？

只要目前較小的那一側還有下一顆可拿，就仍然有機會把 $\min(sa,sb)$ 拉高，因此值得繼續往前走。

但如果：

sa < sb 且 A 已經拿完
或 sb < sa 且 B 已經拿完

那就代表「決定最壞收益的那一側」已經沒有辦法再提升了。這時如果硬要繼續補另一側，只會讓挑選成本增加，而 $\min(sa,sb)$ 仍然不會變大，所以可以直接停止。

程式中的 while 條件，表達的正是這個想法：

兩邊都還有元素時，當然可以繼續
若其中一邊先用完，只有在「尚未用完的那一邊正是較小側」時才值得繼續補

停止條件的本質

不是「任一邊用完就停」，而是「決定答案的較小側用完才停」。

4. 正確性直觀總結

為什麼這個貪心成立？

對任意狀態 $(i,j)$ ：

若 $S_A(i) < S_B(j)$ ，任何只增加 $j$ 的做法都不可能讓答案更好
若 $S_A(i) > S_B(j)$ ，任何只增加 $i$ 的做法都不可能讓答案更好

換句話說，從任意狀態出發，唯一可能通往更好答案的方向，就是擴張當前較小的那一側。雙指標所做的事，就是沿著這條「所有可能有貢獻的路徑」一路掃過去，因此不會漏掉最優解。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$
空間複雜度： $\mathcal{O}(n)$

Code

def solve():
    n = int(input())
    A = [0] * n
    B = [0] * n
    for i in range(n):
        A[i], B[i] = map(float, input().split())

    A.sort(reverse=True)
    B.sort(reverse=True)

    ans = 0
    sa = sb = 0
    i = j = 0
    # 只要目前較小的一側還能繼續補，就還可能讓答案變大
    while (i < n and sa <= sb) or (j < n and sa > sb):
        # 補目前總和較小的一側；補較大的一側只會增加成本
        if sa <= sb:
            sa += A[i]
            i += 1
        else:
            sb += B[j]
            j += 1
        ans = max(ans, min(sa, sb) - i - j)
    print(f"{ans:.4f}")


if __name__ == "__main__":
    solve()