Task
$n$ 个人 $n + 1$ 件物品,每个人 $i$ 对一件物品 $j$ 有一个喜欢程度 $a_{i, j}$。
一轮游戏从 $i$ 开始,按 $i, i + 1, \cdots, n, 1, 2, \cdots, i - 1$ 的顺序每人选走一个物品,每个人都希望他对最后剩下的物品的喜欢程度最大,答案为最后剩下的物品是哪个。对于每个 $i \in [1, n]$ 都求出答案。
对于每个 $i$,$a_{i, 1} \sim a_{i, n + 1}$ 为 $1 \sim n + 1$ 的排列。
$n \le 5000$。
Solution
发现正着想没什么思路,倒过来思考。
为了方便,记 $f_{i, j}$ 表示第 $i$ 个人喜欢程度为 $j$ 的物品编号,即 $f_{i, a_{i, j}} = j$。
假设从第 $i$ 个人开始选物品。
首先考虑最后一个人 $i - 1$。由于轮到他的时候只剩两个物品可选,那么他一定会毙掉他更讨厌的那个物品 $x_{i - 1}$。
再考虑倒数第二个人 $i - 2$。考虑分类讨论如下:
如果剩下的三个物品中 $i - 2$ 号人最讨厌的不为 $x_{i - 1}$,那么他会毙掉他最讨厌的物品 $x_{i - 2}$。
否则,他和最后一个人最讨厌的物品是同一个物品,那么他会选择不毙掉 $x_{i - 1}$,留给最后一个人去将它选走,自己选择倒数第二讨厌的物品。这样的话他就可以保证最后剩下的物品(在还剩下的 $3$ 个物品中)是他最喜欢的。
想到这里,我们可以发现,最后一个人 $i - 1$ 选走的物品一定是他初始最讨厌的物品 $f_{i - 1, 1}$,因为前面的人即使最讨厌的物品也是它也会把该物品留给 $i - 1$ 来选。同理,若 $f_{i - 2, 1} \neq f_{i - 1, 1}$,$i - 2$ 选走的是 $f_{i - 2, 1}$,否则为 $f_{i - 2, 2}$。
于是我们便得出了暴力思路:倒着决策,当前人选走还未被选过的他最讨厌的物品。
暴力是 $O(n^3)$ 的,理论上无法通过,但跑得飞快过了。暴力 Code。
接下来考虑优化。
我们以第 $n$ 个人为例:考虑第一轮从 $1$ 开始操作,第二轮从 $2$ 开始操作,由于我们是倒着决策,那么 $n$ 的决策优先权不断降低。也就是说,假设第一轮 $n$ 最终选了 $f_{n, k_1}$ 这件物品,那么第二轮时 $n$ 选走的物品 $f_{n, k_2}$ 一定满足 $k_1 \le k_2$。
所以我们考虑开一个 $lst_i$ 记录第 $i$ 个人上一轮选择的物品为 $f_{i, lst_i}$,那么当前轮时枚举 $i$ 的决策直接从 $lst_i$ 开始枚举即可。当然,如果 $i$ 是当前轮第一个决策的人,那么强制让他从 $f_{i, 1}$ 开始选。
这样的话每个 $f_{i, j}$ 最多只会被遍历一次,复杂度被降到了 $O(n^2)$,可以通过。正解 Code。