🔗 CF2178D Xmas or Hysteria

rating: 1698

Problem Statement

題目簡述

有 $n$ 個精靈，第 $i$ 個精靈的攻擊力 $a_i$ 與生命值 $h_i$ 初始皆為 $a_i$ （所有 $a_i$ 互不相同）。

戰鬥規則：

每次選擇一個尚未攻擊過且存活的精靈 $x$ 攻擊另一個存活的精靈 $y$
傷害計算： $h_y \gets h_y - a_x$ ，反噬： $h_x \gets h_x - a_y$
重複直到不存在合法的攻擊者

構造一個攻擊序列，使過程結束後恰好有 $m$ 個精靈存活；若無解則輸出 -1。

Constraints

約束條件

$2 \le n \le 2 \cdot 10^5$
$0 \le m \le n$
$1 \le a_i \le 10^9$
所有 $a_i$ 互不相同。

思路：構造 + 排序

核心性質：以卵擊石必自毀

每次攻擊中，攻擊力較小的精靈必死。因為生命值最多等於攻擊力，而對方的攻擊力更大，所以必然被一擊殺死。

因此，每次攻擊至少會導致一隻精靈死亡。存活的精靈必須都攻擊過，而他們的攻擊目標（攻擊力較小的精靈）都會立即死亡。這意味著：

每一隻存活的精靈，都對應一隻被它擊殺的精靈
因此最多只能有 $\lfloor \dfrac{n}{2} \rfloor$ 隻精靈存活

無解條件

若 $2m > n$ ，則無解，輸出 -1。

構造方法

將所有精靈按攻擊力從小到大排序，令排序後的索引為 $0, 1, \ldots, n-1$ 。

一般情況 ( $m > 0$ )

將精靈分為三組：

組別	索引範圍	角色
存活者	$[n-m, n)$	最強的 $m$ 隻，最終存活
目標	$[n-2m, n-m)$	次強的 $m$ 隻，被存活者擊殺
多餘	$[0, n-2m)$	最弱的 $n-2m$ 隻，需自行消滅

構造步驟

多餘精靈自殺：讓精靈 $i$ 攻擊精靈 $i+1$ （ $0 \le i < n-2m$ ），每隻都會被更強的對手反殺
存活者擊殺目標：讓存活者 $n-m+i$ 攻擊目標 $n-2m+i$ （ $0 \le i < m$ ）

特殊情況 ( $m = 0$ )

$m = 0$ 的難點：最強的精靈（索引 $n-1$ ）沒有更強的對手可以殺死它。

解決思路

讓多隻精靈攻擊最強者，累積傷害直到它死亡。最後一擊由倒數第二強的精靈完成，雙方同歸於盡，最後無人生還。

構造步驟

檢查可行性：總傷害 $\sum_{i=0}^{n-2} a_i$ 必須 $\ge a_{n-1}$ ，否則無解
預留最後一擊：將倒數第二強的傷害預留給最終擊殺
消耗多餘傷害：若傷害溢出，剩餘傷害仍 $\ge a_{n-1}$ ，讓最小的精靈們互相攻擊（ $i$ 攻擊 $i+1$ ）
圍攻最強者：剩餘精靈全部攻擊最強者，最後一擊與最強者同歸於盡

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，主要瓶頸在排序上。
空間複雜度： $\mathcal{O}(n)$ 。

Code

def solve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))

    if 2 * m > n:
        print(-1)
        return

    idxs = list(range(n))
    idxs.sort(key=lambda idx: A[idx])
    
    ans = []
    if m > 0:
        ans.extend([(idxs[i], idxs[i + 1]) for i in range(n - 2 * m)])
        ans.extend([(idxs[n - m + i], idxs[n - 2 * m + i]) for i in range(m)])
    else:
        dmg = sum(A) - A[idxs[-1]]
        if dmg < A[idxs[-1]]:
            print(-1)
            return
        dmg -= A[idxs[-2]]
        i = 0
        while i < n - 2 and dmg >= A[idxs[-1]]:
            u, v = idxs[i], idxs[i + 1]
            ans.append((u, v))
            dmg -= A[u]
            i += 1
        for j in range(i, n - 1):
            ans.append((idxs[j], idxs[-1]))

    print(len(ans))
    for u, v in ans:
        print(u + 1, v + 1)

    def check():
        res = n
        hp = A[:]
        vis = [False] * n
        for u, v in ans:
            if vis[u] or hp[u] <= 0:
                return False
            vis[u] = True
            hp[v] -= A[u]
            if hp[v] <= 0:
                res -= 1
            hp[u] -= A[v]
            if hp[u] <= 0:
                res -= 1
        return res == m
    # assert check()

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

寫在最後

PROMPT

這裡什麼都沒有。