← 返回题目列表

Codeforces · 2157/D

D. 十亿玩家游戏

中文机器翻译题面 查看原题
涅墨西斯理论 - 黄昏时分的玫瑰
⠀

您正在关注十亿玩家游戏世界冠军赛。有 $$$10^9$$$ 玩家参加比赛,您想预测您最喜欢的主播 Godflex 的最终排名 $$$p$$$。分析最近的比赛后,您确定 $$$l \leq p \leq r$$$,但您不知道其他任何事情。

游戏内博彩公司提供了 $$$n$$$ 优惠。在第 $$$i$$$ 报价中,博彩公司建议对 Godflex 的最终排名进行 $$$a_i$$$ 估计。对于每个优惠,您必须准确选择以下操作之一:

  • 忽略该提议。
  • 接受报价,声明 $$$p \leq a_i$$$。如果你是对的,你将赚取 $$$|p-a_i|$$$ 机器人币;否则你会损失 $$$|p-a_i|$$$ 机器人币。
  • 接受报价,声明 $$$p \geq a_i$$$。如果你是对的,你将赚取 $$$|p-a_i|$$$ 机器人币;否则你会损失 $$$|p-a_i|$$$ 机器人币。

在您决定如何处理所有优惠后,就会开始真正的十亿玩家游戏。 Godflex 在 $$$[l, r]$$$ 中获得 $$$p$$$ 仓位,然后结算所有报价。

您的总分是您保证获得的机器人币数量,即您在 $$$[l, r]$$$ 中 $$$p$$$ 的所有可能值中获得的最小机器人币数量。找出你能保证的最高可能分数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$) - 博彩公司对 Godflex 在每个报价中的排名的估计。

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

输出

对于每个测试用例,输出一行包含一个整数:您可以保证的最大可能分数。

示例

输入
复制

4
1 1 5
3
2 100 100
50 200
5 1 10
5 7 3 9 1
5 6 10
9 3 1 7 5

输出
复制

0
150
12
13

注意

在第一个测试用例中,只有一个报价。

  • 如果您忽略该优惠,您的分数为 $$$0$$$;
  • 如果您接受声称 $$$p \leq 3$$$ 的报价,您的分数为 $$$-2$$$(当 $$$p = 5$$$ 时达到,这会让您损失 $$$|5-3| = 2$$$ 机器人币);
  • 如果您接受声称 $$$p \geq 3$$$ 的报价,您的分数为 $$$-2$$$(当 $$$p = 1$$$ 时达到,这会让您损失 $$$|1-3| = 2$$$ 机器人币)。

因此最大可能得分为 $$$0$$$。

在第二个测试用例中,最好接受声称 $$$p \geq 50$$$ 和 $$$p \leq 200$$$ 的报价。由于 $$$p$$$ 必须为 $$$100$$$,因此您将获得 $$$|100-50| + |100-200| = 150$$$ 机器人币。