[20240922 模拟赛] 抽卡
Aaron_Romeo
·
·
题解
前言
这是一道结论题。
然而我们亲爱的 DYH 并没有证明这个结论。经过全机房一整天的努力，我们终于得出结论 ——
不会证。
于是有位神仙激动异常地给出了证明。
题目
你在玩一个抽卡游戏，一共有 n 张卡，分数分别是 a_1, a_2, \dots, a_n 。
每次你可以花费 C 的代价，从牌堆中随机抽出一张卡。你可以选择保留这张卡，那么游戏马上结束，你会获得这张卡对应的分数。也可以选择扔掉这张卡，游戏继续进行，扔掉的卡牌不会放回到牌堆中。
你希望最大化你的期望收益，即你的最后的分数减去抽卡的总代价，问最大化的期望收益是多少。你至少需要抽一张卡。
你要回答 q 组询问，每次询问的 C 不同，而卡牌都相同。并且每组询问之间独立。
对于所有数据，保证 1\leq n \leq 2\times 10^5 ， 1\leq q \leq 100 ， 1\leq a_i, C \leq 10^9 。
题解
先将 a 数组从大到小排序。
一般的，定义 dp_s 表示当前牌的集合为 s 时的最优答案，则有状态转移式：
dp_s=\dfrac{1}{|s|}\sum\limits_{i\in s}\max({dp_{s-i},a_i})-C
对任何状态 s 而言，定义垃圾卡为所有 i \in s 且 dp_{s-i}>a_i 的卡 i，其他的卡为好卡。显然好卡是一段前缀。
设 f_i 表示 s 为前 i 个元素时的 dp_s 的值（那么答案即为 f_n），p_i 表示此时最大的好卡编号。
有结论：
对于任意的 2 \le i \le n 满足：
-
p_i\ge p_{i-1}
-
- 如果当前状态有 i 张卡且包含前 p_i 大，其答案也等于 f_i
-
f_i\le f_{i-1}
使用归纳法证明：
当 i=2 时，显然成立。
否则设 2 到 i-1 都满足上述结论，我们来证 i 也满足。
由于结论 2 和 4 有 j\le p_{i-1} 时 a_j\ge f_{i-2}\ge f_{i-1}，得结论 1 和 2。
由结论 3 得：
f_{i-1}=\dfrac{1}{i-1}\sum\limits_{k=1}^{i-1}\max(0,a_k - f_{i-2})+f_{i-2}-C
所以对于结论 3，因为答案上界是 f_i 且可以不取 p_i 之后的部分，情况和只有前 p_i 大的一样，即可以取到 f_i，得证。所以
f_{i}=\dfrac{1}{i}\sum\limits_{k=1}^{i}\max(0,a_k - f_{i-1})+f_{i-1}-C
最后证明结论 4：
因为加入一个小于等于集合内所有元素的元素会使得集合平均值变小，即
$$
\dfrac{1}{i}\sum\limits_{k=1}{i}\max(0,a_k-f_{i-1})\le\dfrac{1}{i-1}\sum\limits_{k=1}^{i-1}\max(0,a_k-f_{i-1})
$$
则我们只需要证
$$
\dfrac{1}{i-1}\sum\limits_{k=1}^{i-1}\max(0,a_k-f_{i-1})\le C
$$
设分段函数 $F(x)=\dfrac{1}{i-1}\sum\limits_{k=1}^{i-1}\max(0,a_k-x)-C$，
则有 $F(f_{i-2})\le 0, f_{i-1}=F(f_{i-2})+f_{i-2}$。
命题变更为证明 $F(f_{i-1})=F(F(f_{i-2})+f_{i-2})\le 0$。
由于连续函数 $F$ 单调递减且最小斜率是 $-1$，所以 $f_{i-2}+F(f_{i-2})$ 一定在函数零点右边，因此得出 $(f_{i-1}, F(f_{i-1}))$ 在 $x$ 轴下面（自己画一下函数图像就懂了），至此证毕。
接下来的具体实现只需要暴力维护 $f$ 和 $p$ 数组就行了，相对于结论的证明来说并不重要。时间复杂复杂度 $O(nq)$。
## 代码
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
const int N = 2e5;
inline int read() {int x; return scanf("%d", &x), x;}
int a[N + 5];
double f[N + 5];
int main()
{
int n = read(), q = read();
for (int i = 1; i <= n; i ++ ) a[i] = read();
std :: sort(a + 1, a + n + 1, std :: greater<int>());
while (q -- )
{
int c = read();
f[0] = 0;
double sum = a[1];
for (int i = 1, p = 1; i <= n; i ++ )
{
while (p + 1 <= i && a[p + 1] > f[i - 1]) sum += a[ ++ p] - f[i - 1];
f[i] = sum / i - c;
sum -= (i - p) * f[i - 1], sum += (i + 1 - p) * f[i];
}
printf("%.9lf\n", f[n]);
}
return 0;
}
```