题目链接: 核心考点: [[数学]]

D. Billion Players Game

时间限制：每测试点2秒
内存限制：每测试点256 MB

问题描述

NemesisTheory - Rose At Nightfall
⠀
您正在关注《十亿玩家游戏》的世界锦标赛。有 $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获得一个在 $[l,r]$ 范围内的位置 $p$，然后所有报价都会结算。

您的总分是您保证能赚取的robocoins数量，即在 $[l,r]$ 中所有可能的 $p$ 值下，您赚取的最小robocoins数量。找出您能保证的最大可能分数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 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$ 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。

💡 核心直觉 (一句话总结)

中位数到所有点绝对值距离之和最小

✅ 正解思路

• 第一次我是暴力写，发现超时之后就想到了中位数

🧠 举一反三 (Pattern)

• 下次看到 "一个点到所有点距离之和最小" -> 想到 中位数

---

💻 代码

```cpp // Problem: CF 2157 D // Contest: Codeforces - Codeforces Round 1066 (Div. 1 + Div. 2) // URL: https://codeforces.com/contest/2157/problem/D // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)

include

using namespace std;

define int long long

int n,l,r; const int N=2e5+7; int a[N];

int check(int x){ int ans=0; for(int i=1;i<=n;i++){ ans+=abs(a[i]-x); } return ans; }

void solve(){ cin>>n>>l>>r; vector v; for(int i=1;i<=n;i++){ cin>>a[i]; v.push_back(a[i]); } sort(v.begin(),v.end()); int pos=v[n/2]; if(l>pos) pos=l; if(r<pos) pos=r;

printf("%lld\n",check(pos));
return ;

}

signed main(){ int t; cin>>t; while(t--){ solve(); } return 0; } ````

重要的数学模型

这道题虽然代码短，但它包含了一个极其重要的数学模型。从这道题中，你可以提炼出以下三个层面的知识：

1. 经典模型：绝对值不等式与中位数 (The "Post Office" Problem)

这是本题最核心的考点。

题目最终转化为：寻找一个 $x \in [l, r]$，使得 $f(x) = \sum_{i=1}^{n} |a_i - x|$ 最小。

• 结论：函数 $f(x) = \sum |x - a_i|$ 在 $x$ 取 中位数 时达到最小值。

• 直观理解：

  • 把 $x$ 想象成要在数轴上建一个邮局，所有 $a_i$ 是住户。

  • 如果邮局在最左边，往右挪一步，所有人的距离之和这就减少 $n$（因为所有人都离你更近了）。

  • 只要你的左边人数 $< $ 右边人数，往右挪就是赚的。

  • 平衡点就在中间（左边人数 = 右边人数）。

• 记忆口诀：

  • 曼哈顿距离 (绝对值之和) $\to$ 中位数

  • 欧几里得距离 (平方和) $\to$ 平均数

  • 切比雪夫距离 (最大值最小) $\to$ 极差中点 $(\min+\max)/2$

2. 凸函数的性质 (Convexity)

你不仅用到了中位数，还用到了 if(l>pos) pos=l; 这种边界判断。这背后是因为 $f(x)$ 是一个 凸函数 (Convex Function)。

• 碗状曲线：$f(x) = \sum |x - a_i|$ 的图像像一个碗（或者说 V 字形）。

• 性质：对于凸函数，如果无约束的最小值点（坑底，即中位数）不在约束区间 $[l, r]$ 内，那么约束区间上的最小值一定在距离坑底最近的那个端点取到。

  • 如果在区间左边，取 $l$。

  • 如果在区间右边，取 $r$。

  • 如果在区间中间，取中位数。

• 学到的点：以后遇到求单峰/单谷函数在区间上的极值，直接“中位数 + 截断 (Clamp)” 即可，不需要三分法 (Ternary Search)。

3. 博弈论中的“Min-Max”转化为“Max-Min”

题目逻辑稍微绕了一下：你要选择策略，然后面对最差的 $p$。

• 通常这种题（赚取 $|p - a_i|$），最优策略总是 “向中间下注”。

  • 对于小的 $a_i$，猜 $p \ge a_i$。

  • 对于大的 $a_i$，猜 $p \le a_i$。

• 这样你的收益函数就变成了 $f(p) = \sum |p - a_i|$。

• 因为你无法控制 $p$，最坏情况就是 $p$ 让这个收益最小。

• 所以题目本质是求 $\min_{p \in [l, r]} \sum |p - a_i|$。

---

总结：你的知识库应新增

[[数学/最优化]] 一维距离最小化问题

1. 问题模版：找一个点 $x$，使得 $\sum |x - a_i|$ 最小。

   • 解法：$x = \text{Median}(a)$。

2. 问题模版变体：找一个点 $x$，使得 $\sum (x - a_i)^2$ 最小。

   • 解法：$x = \text{Mean}(a)$ （平均值）。

3. 带约束情况：如果要求 $x \in [L, R]$。

   • 解法：先求出无约束的最优解 $opt$，然后 $ans = \max(L, \min(R, opt))$ （即 clamp 操作）。