T1
T2
使用一种类似于摩尔投票法的东西(Keven_He 说像,我不太觉得):
将所有人分为两队,设第一队的总攻击力为 \(a\),第二队的总攻击力为 \(b\)。
不妨设 \(a \le b\),求 \(\min(b-a)\)。
很易理解:
因为他们在一个擂台上,而且迟早要打,所以可以意会为一起打。
将 \(sum\) 设为所有人攻击力之和。
要求 \(\min(b-a)\),即要求 \(a\) 与 \(b\) 尽量接近,可以使用 01背包求解:
设 \(sum \div 2\) 为背包容量,每个人的攻击力为同时为体积与价值。
最大价值即为符合要求的 \(a\),而 \(b\) 为 \(sum - a\),则答案为 \(sum - 2\cdot a\)。