摆渡车

题目描述

有 $n$ 名同学要乘坐摆渡车从人大附中前往人民大学,第 $i$ 位同学在第 $t_i$ 分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发,把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总花费 $m$ 分钟(同学上下车时间忽略不计).摆渡车要将所有同学都送到人民大学。

凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?

注意:摆渡车回到人大附中后可以即刻出发。

对于 $100%$ 的数据,$n \le 500$, $m \le 100$, $0 \le t_i \le 4 \times 10^6$

背景

NOIP2018普及T3
这是一道于我而言不太简单的题
虽然大部分细节都想出来了
但是最后还是没能实现整体代码
也许是因为倒序循环不那么容易的缘故
而且一些很重要的细节也没有注意

代码

方案一:DP
$f[i]$表示在第$i$时刻发车的所需的最小浪费时间
$cnt[i]$表示第$i$时刻到达学生的人数
很容易可以看出,$f[i]$的状态只能由$f[j],j\le i-m$转移而来
于是初始状态转移方程就是这个样子的:
$$f[i] = f[j] + \sum_{k=j + 1}^{i-1}(i-cnt[j]\times j)$$
它所表示的意义是,在$j$时刻发车,并且上一趟发车的时刻为$j$

优化①
转移方程可以化简
$$f[i] =f[j] + \sum_{k=j+1}^{i-1}i - \sum_{k=j+1}^{i-1}cnt[j]\times j$$
$$f[i] = f[j] + (i-j+1)\times i - \sum_{k=j+1}^{i-1}cnt[j] \times j$$
后面那个求和式所表达的含义其实就是$j+1$到$i-1$时刻所有到达同学的t[i]的总和
这是明显可以用前缀和优化的
引入$sum$数组,$sum[i] = \sum t[i] \ (t[i] <= i)$
$$f[i] = f[j] + (i-j)\times i - (sum[i] - sum[j])$$

优化②
当$j \le i-2m$时,在时刻$i$与$j$之间可以多发一趟车,而且这样做是不可能更劣的
所以说循环的下界只用枚举到$i-2m+1$即可

优化③
当$i \ge m$时
如果$i$时刻至$i-m+1$时刻间没有任何同学到达,即 $cnt[i] = cnt[i-m]$
那么$i-m$时刻发车肯定不会产生劣的解
因为这一段时间不发车对答案是没有坏的影响的
然而直接扔掉这个状态,会与上一个优化缩小转移范围起冲突
故令 $f[i] = f[i-m]$,防止漏解。

细节①
循环上界为$max(t[i]) + m$

细节②
$cnt$和$sum$数组在读入时即可开始第一步的初始化

1
2
t = read();
++ cnt[t], sum[t] += t;

然后再$O(n)$加一次即可

细节③
转移时有两个地方要注意下界与0的关系

细节④
$f[i]$初始化为$cnt[i] \times [i] - sum[i]$,即视它为第一趟发出的车
不能用MAXN

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main(){
n = read(), m = read(), m2 = m << 1;
for(int i = 1, t; i <= n; ++ i) {
t = read(), ma = max(t, ma);
++ cnt[t], sum[t] += t;
}
for(int i = 1; i < ma + m; ++ i){
sum[i] += sum[i-1], cnt[i] += cnt[i-1];
}
for(int i = 1; i < ma + m; ++ i){
if(i >= m && cnt[i] == cnt[i-m]) {f[i] = f[i-m]; continue;}
f[i] = cnt[i] * i - sum[i];
for(int j = max(0, i - m2); j <= i - m; ++ j){
f[i] = min(f[i], f[j] + i*(cnt[i] - cnt[j]) - sum[i] + sum[j]);
}
}
for(int i = ma + 1; i < ma + m; ++ i) f[ma] = min(f[i], f[ma]);
printf("%lld", f[ma]);
return 0;
}

方案二:记忆化搜索
只要能DP就能记忆化搜索
而且它一般是要比DP更好写的
最大的优点是方便剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//代码非原创
//因为0 <= st-t[i] <= m,因此可以记忆化,把这个作为状态的第二维
//mem[i][j] : 第i个人等了j分钟的最佳方案
int solve(int i, int st)//i:第i个人,st:车到达的时间为st
{
if (i == n+1)//所有人都上车了
return 0;
if (st < t[i])//如果现在的时间没有人,就到下一个人的到达时间
return solve(i,t[i]);
if (mem[i][st-t[i]])//记忆化
return mem[i][st-t[i]];
int sum = 0, j = i;
//车在st出发了
while (j <= n && t[j] <= st)
sum += t[j ++];//所有到达时间在t[i]和st之间的同学要一块儿走
//注意这时的j是没有跟大家一起走的
int best = st*(j-i) - sum + solve(j, st + m);
//车在st之后的时间点出发
for (; j<=n; ++ j){
sum += t[j];
best = min(t[j]*(j-i+1) - sum + solve(j+1, t[j]+m), best);
}
return mem[i][st-t[i]] = best;
}

int main()
{
...
sort(t+1,t+n+1);//显然从小到大按照时间排序更好算
cout << solve(1,0) << endl;
return 0;
}

方案三:斜率优化
暂时还看不懂这个做法,等学了斜率优化再补上