【每日一题】9月8日题目精讲-摆渡车

题号 NC21471
名称 摆渡车
来源 NOIP2018普及组复赛
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

dp，直观的解法是枚举每趟车的发车时间
f[i]表示是i时刻发车，之前的的同学们的最小等车时间。
那么，
j是上一次的发车时间，j-i>=m，x枚举j+1到i之间来等车的所有学生，
这样的复杂度是会超时，考虑优化。
首先，把求和符号拆开一下：
cnt[i]为i时刻及其之前等车的人的数量，sum[i]为i时刻及其之前等车人的ti和。
于是枚举x的循环不需要了，复杂度为O(t^2)
然后我们再来看问题本身，因为发车的次数不限，其实（某一种）最优解中两次发车的时间间隔不会超过2m（如果超过2m，那么我们在这段时间可以再多发一趟车带走一些人答案不会变坏——带走了人答案肯定更好，没有人带走空车来回一趟也不影响答案）。
所有j只需要在i-2m到i-m之间枚举即可，复杂度为O(tm)。（这个复杂度看起来刚好在tle的边缘疯狂试探，可以再考虑优化一下）
可以看到本题中n，m都比较小，我们考虑能不能搞出和nm相关的转移不要围着很大的t转——注意的是，发车时间点未必是t[i]中存在的时间点，所有直接把f的下标含义换了是肯定不行的，但是因为刚刚说的两次发车之间的间隔不会超过2m，也就是说任何一个人等待的时间都不会超过m，那么我们发车时间就可用一个人的等车时间和他等待的时间来表示，f[i][j]表示，t[i]从小到大排序的前i个人等了j的时间就发了一趟车的情况下的前i个人的最小等待时间，他可以和前一个人上的一趟车，也可也新开一趟车。
f[i][j] = min(f[i-1][t[i]+j-t[i-1]] + j, f[i-1][k]+j)
(t[i]+j) - (t[i-1]+k) >= m 即 k<= t[i]+j-t[i-1]-m
直接枚举看的复杂度为
再观察一下，随着j的增大，k的取值范围区间左界不变右界不断变大所以用个前缀最小值来维护就不用枚举kl
复杂度O(nm),这个题得到了完美的解决！

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目9月15日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴