🔗 CF2179E Blackslex and Girls

rating: 1786

Problem Statement

題意摘要

給定 $n$ 個選區以及兩個政黨 A 與 B 的總票數 $x$ 與 $y$ 。每個選區 $i$ 必須滿足以下條件：

該選區總票數 $a_i + b_i \ge p_i$ 。
勝負關係由二進位字串 $s$ 指定： $s_i = 0 \implies a_i > b_i$ ； $s_i = 1 \implies b_i > a_i$ 。
所有選區總票數需恰好為 $\sum a_i = x$ 且 $\sum b_i = y$ 。

請問是否存在合法的票數分配方案？

Constraints

$1 \leq n \leq 2 \cdot 10^5$
$1 \leq x, y \leq 10^9$
$1 \leq p_i \leq 10^9$

思路：貪心(Greedy) + 分類討論

這是一個構造性問題，但我們只需要判斷可行性。我們可以透過檢查一系列的必要條件來解決，若所有必要條件都滿足，則可以證明一定存在解（充分性）。

1. 總票數限制 (Total Capacity)

最基本的條件是，手中的總票數必須足夠支付所有選區的最低人數需求。

條件一

x + y \ge \sum_{i=1}^n p_i

若不滿足，直接輸出 NO。

2. 勝者的最小成本 (Minimum Winner Cost)

對於每個選區，指定勝者必須獲得嚴格多於敗者的票數 ( $w_i > l_i$ )，且總和需達標 ( $w_i + l_i \ge p_i$ )。
為了最小化勝者的消耗，我們考慮極限情況：勝者只贏 1 票 (在 $p_i$ 為奇數時) 或 2 票 (在 $p_i$ 為偶數時)。
由 $w_i \ge l_i + 1$ 且 $w_i + l_i \ge p_i$ ，兩式相加可得：

2w_i \ge p_i + 1 \implies w_i \ge \left\lfloor \frac{p_i}{2} \right\rfloor + 1

這是勝者在單一選區必須投入的「硬性下限」。

我們定義 $min\_req(A)$ 為所有 $s_i=0$ 的選區中，A 作為勝者的最小需求總和；同理 $min\_req(B)$ 。

條件二

x \ge min\_req(A) \quad \text{且} \quad y \ge min\_req(B)

若任一方連基本的勝者門檻都無法支付，則輸出 NO。

3. 全局分配與剩餘票數機制 (Case Analysis)

在滿足上述基本條件後，剩餘的票數可以用來鞏固優勢或填補人數空缺。情況分為兩類：

Case A: 雙方皆有勝場 (Mixed Winners)

若字串 $s$ 中同時包含 ‘0’ 和 ‘1’：

A 的剩餘票數：可以全部投入到任意一個 A 獲勝的選區，這只會讓 $a_i$ 更大，不影響 $a_i > b_i$ 。
B 的剩餘票數：同理，可以全部投入到 B 獲勝的選區。
填補 $p_i$ ：敗者的票數 ( $l_i$ ) 可以是任意值（只要 $l_i < w_i$ ）。若總票數充足，我們可以將多出的票分配給敗者來滿足 $\sum p_i$ 的需求，或者增加勝者的票數。

結論

只要滿足條件一與條件二，且雙方都有勝場，總是能找到分配方案。答案為 YES。

Case B: 單方全勝 (Uniform Winners)

若某一方（例如 A）贏得所有選區 ( $s$ 全為 ‘0’)：

A 的剩餘票數依然可以隨意分配。
關鍵在於 B (全敗方)：B 在所有選區都必須是敗者 ( $b_i \le a_i - 1$ )。這限制了 B 能接收的「最大」票數。
我們必須保證 A 有足夠的票數來壓過 B。對於每個選區， $a_i \ge b_i + 1$ 。
對所有選區求和： $\sum a_i \ge \sum b_i + \sum 1 \implies x \ge y + n$ 。

關鍵判斷

如果只有一方獲勝（例如 A），除了基本條件外，還必須滿足：

x \ge y + n

這是因為每一區 A 至少要比 B 多 1 票，累積起來 A 的總票數必須比 B 多出 $n$ 票。
(若 B 全勝，則需 $y \ge x + n$ )。

複雜度分析

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

Code

def solve():
    n, x, y = map(int, input().split())
    s = input()
    P = list(map(int, input().split()))
    assert len(P) == n

    # 1. 檢查總人數是否足夠覆蓋所有選區的最低要求
    if x + y < sum(P):
        print("NO")
        return

    # 2. 計算勝者所需的最小票數
    # cnt[0] 累積 A 當勝者時的最小需求, cnt[1] 累積 B 當勝者時的最小需求
    cnt = [0, 0] 
    for p, ch in zip(P, s):
        c = ord(ch) - ord('0')
        cnt[c] += (p >> 1) + 1

    # 檢查該黨持有的總票數 x 或 y 是否滿足其作為勝者的最小需求
    if x < cnt[0] or y < cnt[1]:
        print("NO")
        return

    # 檢查能否分配剩餘票數
    if cnt[0] and cnt[1] or cnt[0] and x >= y + n or cnt[1] and y >= x + n:
        print("YES")
    else:
        print("NO")

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

寫在最後

PROMPT

這裡什麼都沒有。