CF1477E&大户爱的送分题题解
0htoAi
2022-06-25 14:30:45
此篇未投洛谷题解，因为写得太菜了qwq。
# CF1477E&大户爱的送分题题解
（CF1477E为我出的校内模拟赛的一道题——《大户爱的送分题》的待修版本）
# 大户爱的送分题
文件名```OhtoAiFirst.cpp/.in/.out```，时间限制 $1$ 秒，空间限制 $256MB$。
注意第一个字母是```O```而不是```0```。
## 题目背景
大户爱去参加一个战争策略比赛，叫做阿克耐次，不过名字并不重要，重要的是她想赢得这个比赛。
## 题目描述
比赛规则如下：
大户爱有 $n$ 个干员，第 $i$ 个干员攻击力为 $a_i$，敌方有 $m$ 个敌人，第 $i$ 个敌人攻击力为 $b_i$。
干员和敌人将按照一定顺序站上评分台（**不一定是一个干员一个敌人**），评分台将会为其表现评分，评分台的评分是累加的，设第 $i$ 个人的战斗力为 $X$，第 $i-1$ 个人的战斗力为 $Y$，则第 $i$ 个人对评分台的贡献为 $X-Y$。设评分台当前累计评分为 $S$，若第 $i$ 个人对 $S$ 贡献完毕之后 $S<0$，则 $S$ 将会置为 $0$。**在此之后**计算第 $i$ 个人的表现分为当前评分台的评分。
* 钦定第一个人的贡献就是她本身的战斗力。
* 评分台初始分数为 $k$。
设大户爱的最终得分为所有干员的评分之和减去所有敌人的评分之和
求最大最终得分。
为了方便理解，设 $c$ 数组为一个可能的站上评分台的顺序（编号从 $1$ 开始），则计算第 $i$ 个人的得分的代码如下：
```
long long GetScore(int i)
{
long long S=k;
for(int j=1;j<=i;j++)
{
S+=c[j]-c[j-1];
if(S<0)
S=0;
}
return S;
}
```
## 输入格式
第 $1$ 行 $3$ 个整数 $n,m,k$。
第 $2$ 行 $n$ 个整数 $a_1$ 至 $a_n$。
第 $3$ 行 $m$ 个整数 $b_1$ 至 $b_m$。
## 输出格式
一个整数，为最终得分的最大值。
## 样例输入1
```
3 4 5
1 2 7
3 4 5 6
```
## 样例输出1
```
-4
```
## 样例输入2
```
7 8 123458
958125 14018 215153 35195 90380 30535 204125
591020 930598 252577 333333 999942 1236 9456 82390
```
## 样例输出2
```
1361307
```
## 数据范围
对于 $5 \%$ 的数据：$ 2\leq n,m \leq 5$。
对于 $30 \%$ 的数据：$2 \leq n,m \leq3 \times 10^3$。
对于 $100 \%$ 的数据：$2 \leq n,m \leq 1 \times 10^6$，$1 \leq a_i,b_i,k \leq 1 \times 10^6$。
## 题解
### Part 1
设 $c$ 数组为一种 $a,b$ 数组的排列方案。
当计分器不重置为 $0$ 时，每个人分数如下：
$1:k$
$2:k+c_2-c_1$
$ 3:k+c_3-c_2+c_2-c_1 =k+c_3-c_1 $
可以得到：
$$
Score_i=k+c_i-c_1
$$
去掉这个限制，显然 $Score_i$ 不会变得更劣。
那么猜想 $Score_i$ 可以表示为：
$$
Score_i=k+c_i-c_1+\Delta
$$
考虑 $\Delta$ 是什么。
初始的时候 $\Delta=0$。
当**第一次** $Score$ 的值小于 $0$ 时，$\Delta$ 为了将 $Score$ 补到 $0$，加上 $0-(k+c_i-c_1)$。
当**第二次** $Score$ 的值小于 $0$ 时，相当于：
$$
Score_i=k+c_i-c_1+0-(k+c_j-c_1)
\\
\because Score_i<0
\\
\therefore k+c_i-c_1+0-(k+c_j-c_1)<0
\\
k+c_i-c_1+0-k-c_j+c_1<0
\\
c_i-c_j<0
\\
c_i<c_j
$$
（上式 $i$ 为当前位置，$j$ 为第一次 $Score$ 小于 $0$ 时的位置）
显然可以得到，当 $\Delta$ 被更新，当且仅当当前 $c_i$ 比上一次更新时的 $c_j$ 值小。
根据 $\Delta$ 的更新原则，第 $i$ 位的 $\Delta=0-(k+c_{min}-c_1)$，其中 $min$ 为 $i$ 及之前的 $c$ 的最小值的下标。
需要注意的是只有当第一次 $Score$ 的值小于 $0$ 及之后 $\Delta$ 才会有值。
为了方便后面的计算，将 $Score_i$ 化成如下形式：
$$
Score_i=k+c_i-c_1+\max(0,c_1-c_{min}-k)\\
\Delta=\max(0,c_1-c_{min}-k)
$$
（其中 $min$ 的意义同上）
### Part 2
显然如果枚举全排列过不去，开始贪心。
首先先不管 $c_1$ 的情况，即目前 $c_1$ 确定。
题目要求让 $a$ 数组的 $Score$ 和减去 $b$ 数组的 $Score$ 和尽量大，用 $Score$ 计算公式的理论最大答案为多少？
显然每个 $k+c_i-c_1$ 是不可避免的，于是问题转移到了 $max(0,c_i-c_{min}-k)$ 上，即问题转移到了 $\Delta$ 上。
贪心地选择，显然对于 $a$ 数组的每个值，$\Delta$ 要尽量大，又因为 $c_i$ 和 $k$ 固定，所以只能让 $c_{min}$ 尽量小，即 $c_{min}=\min(a_{min},b_{min})$，得到 $Score_i=k+c_i-c_1+\max(0,c_1-\min(a_{min},b_{min})-k)$。（这里及下文的 $a_{min}$ 表示 $a$ 中最小值，$b_{min}$ 表示 $b$ 中最小值）。
对于 $b$ 数组的每个值，$\Delta$ 要尽量小，同样因为 $c_i$ 和 $k$ 固定，所以只能让 $c_{min}$ 尽量大。由于 $c_{min}$ 绝对单调不上升，即 $c_{min}\leq c_i$，所以最劣情况是 $c_i=c_{min}$，得到 $Score_i=k+c_i-c_1+\max(0,c_1-c_{i}-k)$。
只需要构造出一个排序方式使得满足以上条件就好了。
这里给出一种合法构造：$c_1$ 固定，剩下的 $b$ 数组的元素从大到小排序接到 $c_1$ 后面，剩下的 $a$ 数组元素从小到大排序接到 $b$ 数组后面，此时的 $c$ 序列是关于$c_1$ 的最优序列。
#### 证明:
* 对于前半部分，也就是 $b$ 数组部分：
因为 $b$ 数组递减，所以 $c_{min}$ 只会是 $c_1$ 和 $c_i$ 之间的一个，所以：
$$
Score_i=k+c_i-c_1+\max(0,c_1-\min(c_1,c_i)-k)
$$
当 $\min(c_1,c_i)=c_1$ 时，$c_1-min(c_1,c_i)-k\leq 0$，同时 $c_1-c_i-k \leq 0$。即此时 $\Delta $ 的值只能为 $0$，所以可以把 $min(c_1,c_i)$ 化掉，即：
$$
Score_i=k+c_i-c_1+\max(0,c_1-c_i-k)
$$
成立。
* 对于后半部分，也就是 $a$ 数组的部分：
因为 $a$ 数组递增，所以对于后半部分的每一个位置，$c_{min}$ 都是 $\min(a_{min},b_{min})$，即：
$$
Score_i=k+c_i-c_1+\max(0,c_1-\min(a_{min},b_{min})-k)
$$
成立。
### Part 3
式子合并。
对于固定的 $c_1$：
设 $c_1=t$
* 若 $c_1$ 选的 $a$ 的值，将其从 $a$ 数组中清除后：
$$
ans=k+\sum_{i=1}^{n-1} k+a_i-t+\max(0,t-\min(a_{min},b_{min})-k)-\sum_{i=1}^m k+b_i-t+\max(0,t-b_i-k)
\\
=(n-m)k+(m-n+1)t+(n-1)\max(0,t-\min(a_{min},b_{min})-k)+\sum_{i=1}^{n-1}a_i-\sum_{i=1}^{m}b_i+\max(0,t-b_i-k)
\\
$$
前面一坨是 $O(1)$ 的，由于 $b$ 单调递增，最后一个 $\max(0,t-b_i-k)$ 可以二分枚举断点。
* 若 $c_1$ 选的 $b$ 的值，同上：
$$
ans=-k+\sum_{i=1}^{n} k+a_i-t+\max(0,t-\min(a_{min},b_{min})-k)-\sum_{i=1}^{m-1} k+b_i-t+\max(0,t-b_i-k)
\\
=(n-m)k+(m-n-1)t+n \times \max(0,t-\min(a_{min},b_{min})-k)+\sum_{i=1}^{n}a_i-\sum_{i=1}^{m-1}b_i+\max(0,t-b_i-k)
$$
# CF1477E
（就是可以修改 $k$，$a$，$b$ 的《大户爱的送分题》）
### Part 4
玄学的一步。
对了很多组拍，发现答案的 $c_1$ 取值大都集中在 $a_{min}$，$b_{min}$，$b_{max}$ 处，但是又有些时候是没什么规律的 ，然后看了一眼别人题解，说的是 $c_1$ 还可以为 $b$ 中次大值加 $K$ 在 $a$ 的前驱和后缀（[这个题解](https://www.luogu.com.cn/blog/Troverld/solution-cf1477e)） 所以相当于只需要算这 $5$ 个点的值就行了。
前缀和可用树状数组维护。
二分断点可用平衡树维护，其实手写平衡树很方便，set 不能查排名就很难搞。
注意如果 $c_1$ 为 $a_{min}$ 或 $b_{min}$ 则算式里的 $a_{min}$ 或 $b_{min}$ 是指其**次小值**。.
更改数值就是平衡树上删除原数值再插入新数值，再更改树状数组单点值就好。
## 附：
我只过了我自己出的不带修版本，CF1477E 因为要写平衡树所以没来得及做，所以 Part 4 不保证是对的，因为是看的别人的题解。只能说大概率是对的。