CF2157D.Billion Players Game

NemesisTheory - Rose At Nightfall

⠀

你正在关注亿人游戏（Billion Players Game）世界锦标赛。有 $10^9$ 名选手参加，你想预测你最喜欢的主播 Godflex 的最终排名 $p$。经过最近比赛情况的分析，你确定 $l \leq p \leq r$，但除此之外，没有更多的信息。

比赛的游戏内博彩公司提供了 $n$ 个“竞猜”机会。在第 $i$ 个竞猜中，博彩公司给出 Godflex 排名的预测值 $a_i$。对于每个竞猜，你必须选择以下三种操作之一：

• 忽略这次竞猜；
• 接受竞猜并断言 $p \leq a_i$。如果你的断言正确，你将获得 $|p-a_i|$ robocoins，否则你将失去 $|p-a_i|$ robocoins；
• 接受竞猜并断言 $p \geq a_i$。如果你的断言正确，你将获得 $|p-a_i|$ robocoins，否则你将失去 $|p-a_i|$ robocoins。

你对所有竞猜机会做出操作后，实际比赛才会进行。Godflex 的排名 $p$ 将会在区间 $[l, r]$ 内选出，然后所有竞猜结算。

你的总得分是你无论如何都能保证获得的 robocoins 数量，即在所有可能的 $p \in [l, r]$ 范围内，你能够保证获得的 robocoins 的最小值。请你计算你能够保证的最大得分。

每个测试用例包含多组数据。第一行为测试用例组数 $t$（$1 \le t \le 10^4$）。每组数据描述如下：

每组测试用例的第一行包含三个整数 $n$、$l$、$r$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq l \leq r \leq 10^9$），分别表示竞猜次数以及 Godflex 最终排名的可能区间。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示博彩公司为每次竞猜给出的排名估计。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示你能够保证的最大得分。

第一组数据中只有一次竞猜：

• 如果你忽略该竞猜，你的得分为 $0$；
• 如果你接受了竞猜并宣称 $p \leq 3$，你的得分为 $-2$（当 $p = 5$ 时你将失去 $|5-3| = 2$ robocoins）；
• 如果你接受了竞猜并宣称 $p \geq 3$，你的得分为 $-2$（当 $p = 1$ 时你将失去 $|1-3| = 2$ robocoins）。

因此最大保证得分为 $0$。

在第二组数据中，最优策略是接受竞猜并宣称 $p \geq 50$ 以及 $p \leq 200$。由于 $p$ 必须为 $100$，你将获得 $|100-50| + |100-200| = 150$ robocoins。

由 ChatGPT 5 翻译