流血-净化博弈
一名刺客攻击一名牧师，刺客有 \(n\) 种武器，每种武器都可以随时使用，但只能被使用一次。刺客在使用第 \(i\) 种武器后，立即对目标施加持续时间为 \(t_i\) 的流血效果：随后在 \(t_i\) 时间内，目标每单位时间匀速受到 \(d_i\) 点伤害。不同武器施加的效果可同时存在并生效。牧师可以释放净化技能，释放后清空自身所有流血效果，冷却时间为 \(c\)，即两次释放之间的时间间隔至少为 \(c\)，且初始时可以立即释放净化技能，可以在观察到攻击后于同一时刻立即净化。
以上信息双方均已知。刺客的目标是最大化目标受到的伤害，牧师的目标是最小化自身受到的伤害。记 \(p_i = d_i t_i, q_i = d_i \min (t_i, c)\)。
- 求双方的最优策略，以及最优策略下，刺客造成的伤害。
解答
每件武器在完全不被净化时造成的总伤害为 \(p_i=d_it_i\)；任何一件在第一次净化之后使用的武器 \(i\)，在下一次净化前至多生效 \(c\) 时间，故其伤害至多为 \(q_i = d_i \min (t_i, c)\)。显然 \(p_i\ge q_i\)。
将武器按 \(q_i\) 非递减排列。设排列为 \(\pi\)，即
\[ q_{\pi_1}\le q_{\pi_2}\le\cdots\le q_{\pi_n}. \]
定义
\[ A_k = \sum_{j<k}p_{\pi_j} + \sum_{j>k}q_{\pi_j}, \qquad 1\le k\le n. \]
那么博弈值，即最优策略下刺客造成的总伤害，为
\[ { V=\min_{1\le k\le n} \left( \sum_{j<k}d_{\pi_j}t_{\pi_j} + \sum_{j>k}d_{\pi_j}\min(t_{\pi_j},c) \right). } \]
也可以写成
\[ { V=\min_{1\le k\le n} \left( \sum_{j<k}p_{\pi_j} + \sum_{j>k}q_{\pi_j} \right). } \]
这里第 \(k\) 件武器可理解为被牧师的第一次净化“牺牲掉”的武器。
刺客的最优策略
刺客按 \(q_i\) 非递减顺序使用武器：
- 使用武器 \(\pi_1\)；
- 如果牧师没有净化，就等该武器的流血效果自然结束，再立即使用 \(\pi_2\)；
- 如此继续；
- 一旦牧师释放第一次净化，就在净化释放之后立即同时使用所有尚未使用的武器。
设牧师第一次净化是为了清除武器 \(\pi_k\)：
- 前 \(k-1\) 件武器的效果已经自然结束，共造成 \(\sum_{j<k}p_{\pi_j}\) 点伤害；
- 武器 \(\pi_k\) 可在同一时刻被立即净化，因而可以造成 \(0\) 点伤害；
- 刺客在这次净化之后立刻使用剩余武器。由于下一次净化至少要等待 \(c\)，每件剩余武器 \(\pi_j\) 至少造成 \(q_{\pi_j}=d_{\pi_j}\min(t_{\pi_j},c)\) 点伤害。
因此总伤害至少是
\[ A_k= \sum_{j<k}p_{\pi_j} + \sum_{j>k}q_{\pi_j}. \]
无论牧师在哪一件武器处进行第一次净化，刺客都能保证至少造成
\[ \min_k A_k=V \]
点伤害。
如果牧师在某件武器生效过程中、而不是刚使用时净化，那么该武器在净化前还会额外造成一部分伤害，不会使刺客收益变少。
牧师的最优策略
牧师的策略分成两个阶段。在第一次净化之前，牧师保留初始可用的净化，根据刺客已经使用的武器及已经受到的伤害，选择恰当的武器作为“牺牲品”立即净化。一种在线描述如下。记：
- \(D\) 为目前已经受到的伤害；
- \(U\) 为刺客尚未使用的武器集合；
- \(R=\sum_{i\in U}q_i\)。
当刺客使用新武器后，如果 \(D+R\le V\)，牧师立即净化。因为当前刚使用的武器会在同一时刻被清除，不造成伤害；第一次净化之后，牧师再通过周期净化，可以把所有尚未使用武器带来的总伤害控制在 \(R\) 以内。因此最终伤害不超过 \(D+R\le V\)。
如果上述条件尚未满足，牧师继续保留净化。由下面的排序最优性可知，无论刺客以何种顺序、何种时机攻击，牧师总能在总伤害超过 \(V\) 之前找到这样的净化时机；如果刺客停止继续使用武器，则已有武器最终造成的总伤害也不超过 \(V\)。
第一次净化在时刻 \(s\) 释放后，牧师每当冷却结束就立即再次净化，即在
\[ s+c,\ s+2c,\ s+3c,\ldots \]
释放净化。
于是任何一件在第一次净化之后使用的武器 \(i\)，在下一次净化前至多生效 \(c\) 时间，故其伤害至多为
\[ d_i\min(t_i,c)=q_i. \]
所以第一次净化之后所有尚未使用武器造成的伤害总和至多为其 \(q_i\) 之和。
最优性证明
考虑一个给定的武器排列。若第 \(k\) 件武器被第一次净化清除，则刺客的保证收益是
\[ \sum_{j<k}p_{\pi_j}+\sum_{j>k}q_{\pi_j}. \]
现在只考察相邻的两件武器 \(a,b\)。忽略它们之前和之后的公共项：
- 若顺序为 \(a,b\)，两者对应的最坏收益部分为 \(\min(q_b,p_a)\)
- 若顺序为 \(b,a\)，对应为 \(\min(q_a,p_b)\)
若 \(q_a\le q_b\)，由于 \(p_a\ge q_a\) 且 \(p_b\ge q_b\ge q_a\)，有
\[ \min(q_b,p_a)\ge q_a=\min(q_a,p_b). \]
因此，把较小的 \(q\) 放在前面不会使刺客的最低保证收益下降。不断交换逆序对后，得到最优排列
\[ q_{\pi_1}\le q_{\pi_2}\le\cdots\le q_{\pi_n}. \]
求出博弈最优值需要计算 \(p_i, q_i\)、排序和扫描求最小值，整体时间复杂度为 \(O(n \log n)\)。