P10712 解题报告
船酱魔王
·
·
题解
题意回顾
运输的代价为你装载至少一个球的总里程。
$ 1 \le n,c \le 1000 $。
## 分析
### 初步想法
本题是我校一次校内 CSP-S 备赛练习的第四题，分析题面后我初步判断这道题可能是动态规划，还需要一定贪心优化思想，故从简单情况考虑贪心方法再行设计。
### Task 1：$ c=1 $（16 分）
这个问题可以转化为，一条线上有一些红点和蓝点，一一配对连线的最小总连线长度是多少。
考虑两个相邻的点之间，如果这条线段左面（含边界）蓝点和红点差值为 $ x $，则必然会有至少 $ x $ 个点配对需要跨过这条线段。
考虑如何达到这个最优解？红点蓝点排序后一一对应。此时对于每个这样的线段，左侧红点蓝点可以尽量互相“抵消”，此时只会有差值个点越过这条线段连线。
故排序 $ a,b $ 数组后一一输出即可。
### Task2：$ a_i \le 5000,b_i > 5000 $（22 分）
下文中，记 $ a,b $ 为从小到大排序后的数组。
沿用 Task1 的思路，$ |b_1-a_n| $ 会被跨越过 $ \lceil \frac{n}{c} \rceil $ 次。
考虑在这 $ \lceil \frac{n}{c} \rceil $ 次运输中，第 $ i $ 次最左侧的球号为 $ t_i $，最右侧的洞号为 $ s_i $。
故答案为 $ \sum |-a_{t_i}+b_{s_i}| = \sum b_{s_i} - \sum a_{t_i} $。
因此，我们要尽量让每个 $ b_{s_i} $ 和 $ -a_{t_i} $ 最小，即尽量最小化 $ s_i $ 最大化 $ t_i $，考虑从小到大排序 $ t $ 数组，从大到小排序 $ s $ 数组，此时 $ s_1=n,t_1=1 $，考虑 $ t_i $ 的最大值为 $ t_i=1+(i-1)c $，$ s_i $ 的最小值为 $ s_i=n-(i-1)c $，因为必须取完 $ a_2 \sim a_{t_2-1} $ 才能使得 $ t_2 $ 为之后最靠左的球点号，$ s $ 数组同理。取到最优方案的方法是每次取最靠左最靠右的最多 $ c $ 个点匹配。
### Task3A：求出最小花费（31 分）
考虑沿用 Task1 的思路，两个相邻点之间的线段被覆盖的次数最小值为左侧红蓝点差值 $ x $ 计算出 $ \lceil \frac{x}{c} \rceil $ 的值。
故答案为 $ \sum x_i(d_{i+1}-d_i) $，$ d_i $ 为线段 $ i $ 左侧点的坐标。
### Task3B：求出最优方案（31 分）
考虑设计最优的方案，取到这个下界，对于一次运输，设方向为左到右（$ x_i $ 为负的话反过来就行了），则需要尽量保证对于所有非负的 $ x_i $，能运完就运完，否则跨过这条线段运 $ c $ 个球。求出运输量 $ \Delta x_i $ 判断两个相邻的线段之间是否运输量相等即可推出中间的点要不要运输（载货或卸货）。
如果 $ x_i \le c $，那么之前可以运输的必然在范围内都运输完了；否则之前必然有至少 $ c $ 个球被运过去，也能使得答案取到最小值。且 $ x_i $ 相邻差一，必然载货和卸货是互相匹配的。
暴力处理并输出即可，时间复杂度为 $ O(n^2) $。
自此，本算法期望得到本题的所有分数。
### Task4：可以加强吗？
考虑本题需要维护的操作：
* 全局操作 $ x_i \leftarrow \max\{0,x_i-c\} $。
* 寻找 $ 0 < x_i \le c $ 的位置，并输出。
可以线段树维护区间还有效的 $ x_i $ 的最小值，均摊复杂度为 $ O(n \log n) $。
复杂度证明：对于一个区间，若全局超过 $ c $ 则可以打标记，对于所有需要往下检查的结点都是由小于等于 $ c $ 变为 $ 0 $ 的，故每个结点最多被检查一次，时间复杂度上限为 $ O(n \log n) $。
数据范围可以支持到 $ n,c \le 10^6 $。
### 总结
本题是一道一维空间上的类哈密顿问题，处理这种问题可能需要找到一些最小化的放缩方法，再考虑能否取到下界。
对于（类）哈密顿问题，除了通用问题下的状压 DP，如果问题求解在树或数轴这种复杂度小于二维平面的结构可以考虑贪心并放缩证明下界，如果求解在标准二维结构复杂度及以上的结构上的话考虑依据结构特点设计动态规划。
对于一维结构（或准一维结构），我们经常使用区间动态规划完成，实例是 2023 年 NOI 春季测试的任务三。
从本题的思考流程上，先是由最简单的方法想到计算每个间隔段对答案的次数贡献，再由跨过中线的任务想到最小化贡献的思路，通过实现来输出最小化答案的方案。
## AC 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
const int N = 1005;
int n, c;
int a[N], b[N];
pair<int, int> pr[N * 2];
int p[N * 2];
int e[N * 2];
int ans = 0;
vector<int> vec;
int main() {
scanf("%d%d", &n, &c);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), pr[i] = (pair<int, int>){a[i], 1};
for(int i = 1; i <= n; i++) scanf("%d", &b[i]), pr[n + i] = (pair<int, int>){b[i], -1};
sort(pr + 1, pr + 2 * n + 1);
int pre = 0;
for(int i = 1; i <= 2 * n; i++) {
pre += pr[i].second;
p[i] = pre;
}
for(int si = 1; si <= n; si++) {
int ok = 0;
for(int i = 1; i <= 2 * n; i++) {
ok += (p[i] <= 0);
if(p[i] <= 0) e[i] = 0;
else e[i] = min(p[i], c), p[i] = max(p[i] - c, 0);
}
if(ok == 2 * n) break;
for(int i = 1; i <= 2 * n; i++) {
ans += (int)(e[i] > 0) * (pr[i + 1].first - pr[i].first);
if(e[i] != e[i - 1]) vec.push_back(pr[i].first);
}
}
for(int si = 1; si <= n; si++) {
int ok = 0;
for(int i = 1; i <= 2 * n; i++) {
ok += (p[i] == 0);
if(p[i] == 0) e[i] = 0;
else e[i] = min(-p[i], c), p[i] = min(p[i] + c, 0);
}
if(ok == 2 * n) break;
for(int i = 2 * n; i >= 1; i--) {
ans += (int)(e[i] > 0) * (pr[i + 1].first - pr[i].first);
if(e[i] != e[i - 1]) vec.push_back(pr[i].first);
}
}
printf("%d\n", ans);
for(int i = 0; i < vec.size(); i++) printf("%d ", vec[i]);
puts("");
return 0;
}
```