题解 P5017 【摆渡车】
sujingmeng · · 题解
解题感想
这道题的质量极好，根据不同的测试数据，由简入难，涵盖了NOIP普及组需要掌握的好几个算法。
题目分析
仔细读题之后，先考虑输入数据。
输入数据当中乘客到达时间数据的输入顺序与解题无关，只有到达时间与解题有关。因此输入的时候，可以按照到达时间直接做输入数据数组。
需要理解的点：乘客上车之后就算完成任务，记录等待时间只包括上车之前的等待时间。
补充： 观察数据，对于后面两组测试点，tmax 明显大，n 相对比较小。这种情况如果用数组存储，空元素太多，反而不利于查找。所以用 map 存储更合适。
情况一：m==1
对于 m==1，实际上每趟都能接到乘客，因此完全不需要等待，直接输出 0。
情况二：n <= 20 && m==2
对于 n<=20 && m==2，这时候可以针对每一个乘客到达的时间点和送完乘客之后返回的时间点做 “发车” 或者 “不发车” 的深度搜索，既然 n<=20 && m==2，因此搜索深度不超过10。
第一次测试的时候，发现 bus3 运行不出来。 然后注意到 n 比较大，因此需要对没有人到达的时候的发车情况做剪枝。 就是当没有人等车的时候，就不做发车分支的探测了，只做当时不发车，等到有乘客了再发车的探测。
实际运行发现：
// bus4 数据迭代了 15k 次。
// bus5 数据迭代了 770k 次。
// bus6 数据迭代了 317k 次。
情况三：n<=500 && m<=100 && 0<=t<=10^4
DP？或者记忆化搜索？好像都行，先讨论 DP。
使用两维数组。 第一维是从 0 开始记的时间。 第二维是从当前时刻开始（包括当前时刻）下一班车从现在计算拖后几分钟出发。 DP当中记录的数据，是记录这种情况下的总等待时间。
动态规划需要按照时间逆序计算，从 tmax 开始向前一直推到 0 时刻。
在 DP 数组设计的时候，有一个要注意的地方。 就是从一次发车，到下次发车，最长的间隔时间为 2*m-1。 理由是：当前时间发车之后 m 分钟回到发车地点。 这时候不一定马上发车。 有可能下面几分钟当中有客人到达，那时候发车总等待时间更短。 比如下面的情况：
m=2
| 时间 | 到达人数 |
|---|---|
| 1 | 3 |
| 2 | 1 |
| 3 | 0 |
| 4 | 3 |
| 5 | 0 |
| 6 | 0 |
在时间点 1 发车，时间点 3 回来。这时候有一个人等待。
在时间点 3 马上发车不是好方法，应该等到时间点 4 更合适。
为什么要记到 2m 呢？
是因为计算 dp[t] 的时候，最好只依赖 dp[t+1]。
如果只依赖dp[t+1]，则可以通过滚动数组做存储。
【这个是后话，应该只有最后一组数据需要压缩存储空间。】
状态转移公式是：
- 对于每一个时刻的当时发车 [t][0]，是从 dp[t+1][m-1] ~ dp[t+1][2*m-1] 之中取最小值。意思是，如果现在发车，并且这次发车回来之后最多拖 m 时间发车的状态中，等待时间最少的那个。
- 对于拖后发车（j=1~m-1） dp[t][j] = dp[t+1][j-1] + 当前时刻到达人数 * j。既然拖了这么长时间发车，那当前时刻到达的乘客就要等 j 分钟。
情况四：n<=500 && m<=10 && 0<=t<=4*10^6
当 t 取值范围非常大的时候，人到达的时间就非常稀薄了。
比如这个取值，如果每个人到达的时间间隔比较远，也就是每个人都专车送，只涉及到不超过 5000 分钟。
比起 400万 的总 t 时间都是很稀少的。
也就是说，时间轴上有大量的超过 2m 的时间点是完全没有乘客到达的。
为什么要讨论 “超过2m” 的时间？是因为发车之后回来需要 m 时间。 如果下一批乘客在接下来的 m 时间内到达，就有可能需要等。 但是如果下一批乘客到达的时间超过 m，那就不妨先发一班车。
所以，可以构造一个新的到达时间序列，把凡是两个乘客到达时间超过 2m 的情况直接压缩到 2m 时间。 这样对新序列的计算结果与原来的时间序列得到的结果相同。 考虑到 n<=500, m<=10，那新序列的时间轴就不超过 10^4，与情况三相同。
情况五：n<=500 && m<=100 && 0<=t<=4*10^6
DP
如果用情况四的方法，然后 DP 使用滚动数组存储数据，至少在 memory 上是够的。
记忆化搜索
这道题用记忆化搜索，对时间和空间的需求更小。
引理：只有两个时间点有发车的必要：一个是有乘客到达等车地点的时间点；另一个是车送完上一波乘客回到发车点的时候。其他时候，不需要发车。
如果我们做一个二维的记忆化搜索，搜索函数定义为：
int dfs_memory(int tm, int cs)
其中 tm 是时间，cs 是该时间点等待的乘客。
意思是：交给 search 函数一个任务， 在 tm 时间点有 cs 个乘客在等车（函数不用管这些等车的乘客是刚好在 tm 到达的还是已经等了一段时间的）， 要求函数计算出这种条件下完成所有运送任务的最小等待时间。
编程中发生过的漏洞
- 在 DFS 的时候，讨论当时发车的分支。
如果这时候没有人等待，则根本不需要当时发车，这一支要剪掉。 否则搜索的深度太深，很多完全没有人到达的时间点也被搜索。 - DP 算法当中，第二维深度取 2m 是重点。
第一版代码就是只取了 m，这样 t[i][0]=t[i+1][m-1]，看起来很对。
但是这样就固定了送人的车回来之后必须马上发车。 实际上为了等后面有可能到的乘客，可以最多拖 m 时间发车。 - type4 考虑过两种算法。其中一种是把数据分节计算。 后来发现直接做压缩状态更好。
- 记忆化搜索需要用到 map 的特性。 最重要的特性是 map 当中的 key 是已经排序好的。 另外，lower_bound 和 upper_bound 的特性得熟悉。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<map>
using namespace std;
int n,m; // 等车人数，往返时间。
int tim[10005]; // 每个时间点到达的等车人数
int mt=0; // 到达时间的最大值
map<int,int> mtime; // 用 map 存储的到达时间和人数的对应关系表
/**
tim 和 mtime 的关系：
当到达时间少于 10000 的时候，输入数据直接进 tim。
当到达时间超过 10000 的时候，先输入 mtime，然后转化到 tim。
*/
// 普通 DFS 测试：
// bus3 数据测试，迭代了 47k 次。
// bus4 数据迭代了 15k 次。
// bus5 数据迭代了 770k 次。
// bus6 数据迭代了 317k 次。
int dfs_normal(int tm, int cs)
// tm:可以发车的最早时间；cs: tm 时间点的等待人数
{
if(tm > mt) {
return 0;
}
int i;
// 测试如果当时发车的情况。
// 注意，由于 n 会到 100，所以如果没人等车也做当时发车的测试，递归会非常深。
// 所以必须做当时发车的剪枝，就是如果没人等着，就不做当时发车的测试。
int fache = 2000000000;
if(cs > 0) {
int waitman = 0;
int waitime = 0;
for(i=tm+1; i<=tm+m; i++) {
waitman += tim[i];
waitime += tim[i] * (tm+m-i);
}
fache = waitime + dfs_normal(tm+m, waitman);
}
int bufache = 2000000000;
for(i=tm+1; i<=mt; i++) {
if(tim[i] > 0) {
break;
}
}
if(i<=mt) {
bufache = cs * (i-tm) + dfs_normal(i, cs + tim[i]);
}
return min(fache, bufache);
}
int type2()
{
int cost;
cost = dfs_normal(0,tim[0]);
return cost;
}
int dpdata[10005][205];
// dp 存储区域，第一维是时间，第二维是从此刻起拖延几分钟发车。
int type3()
{
int retval = 2000000000;
for(int i=mt; i>=0; i--) {
for(int j=0; j<2*m; j++)
{
if(j==0) {
int minm=2000000000;
for(int k=m-1; k<2*m; k++) {
minm=min(minm,dpdata[i+1][k]);
}
dpdata[i][j]=minm;
} else {
dpdata[i][j] = dpdata[i+1][j-1] + j*tim[i];
}
if(i==0) {
retval = min(retval, dpdata[i][j]);
}
}
}
return retval;
}
int type4()
{
map<int, int>::iterator iter;
int left = 0;
int ithis = 0;
// 注意，type4 相当于重构一个与原始数据结果相同的数据集。所以，mt要复位重新算。
mt=0;
for(iter=mtime.begin(); iter!=mtime.end(); iter++) {
if(left == 0) {
ithis = 0;
tim[ithis] = iter->second;
left = iter->first;
}
// 如果两个相邻到达的乘客到达时间的间隔超过 2*m，则压缩到 2*m。
if( iter->first - left > 2*m ) {
ithis += 2*m;
tim[ithis] = iter->second;
left = iter->first;
} else {
ithis += iter->first - left;
tim[ithis] = iter->second;
left = iter->first;
}
mt=max(mt, ithis);
}
// 重构 tim 数组之后，调用 type3 求解。
return type3();
}
// 这个函数，是计算记忆化搜索的 map 的 key。
inline int getindex(int tm, int cs)
{
return tm*500+cs;
}
// 记忆化搜索的存储 map。其中 key 是用到达时间和等待人数组合而成的。
map<int, int> dfsdata;
int dfs_memory(int tm, int cs)
{
// 记忆化搜索是直接用 map 的原始数据，mt 是最大时间。
if(tm > mt) {
return 0;
}
map<int,int>::iterator itera;
itera = dfsdata.find(getindex(tm,cs));
if(itera != dfsdata.end()) {
// 找到历史数据
return itera->second;
}
// 测试如果当时发车的情况。
int fache = 2000000000;
if(cs > 0) {
int waitman = 0;
int waitime = 0;
map<int,int>::iterator iterb;
// upper_bound 是找大于 tm 的最小值。
for(iterb = mtime.upper_bound(tm); iterb != mtime.upper_bound(tm+m); iterb++) {
waitman += iterb->second;
waitime += iterb->second * (tm + m - iterb->first);
}
fache = waitime + dfs_memory(tm+m, waitman);
}
int bufache = 2000000000;
map<int,int>::iterator iterc;
iterc = mtime.upper_bound(tm);
if(iterc != mtime.end()) {
bufache = cs * (iterc->first - tm) + dfs_memory(iterc->first, cs + iterc->second);
}
fache = min(fache, bufache);
dfsdata[getindex(tm,cs)] = fache;
return fache;
}
int type5()
{
return dfs_memory(0,0);
}
int main()
{
// freopen("bus.in","r",stdin);
// freopen("bus.out","w",stdout);
int t;
cin>>n>>m;
if(m==1) {
cout<<0<<endl;
return 0;
}
if(m==2 && n<=20) {
for(int i=0; i<n; i++)
{
cin>>t;
tim[t]++;
mt=max(mt,t);
}
cout<<type2()<<endl;
return 0;
}
for(int i=0; i<n; i++) {
cin>>t;
mtime[t]++;
mt=max(mt,t);
}
if(mt<=10000) { // type3
map<int, int>::iterator iter;
for(iter=mtime.begin(); iter!=mtime.end(); iter++) {
tim[iter->first] = iter->second;
}
cout<<type3()<<endl;
return 0;
}
if(m<=10) { // type4
cout<<type4()<<endl;
return 0;
}
cout<<type5()<<endl;
return 0;
}