【DTOJ #1556】【Luogu P3076】【USACO13FEB】出租车Taxi

题意(来自洛谷):

长度为$m$的栅栏上,有$n$头牛需要坐车前往别的地方,起点和终点分别为$a_i$和$b_i$。现在一辆出租车从最左端$0$出发,要运送完所有牛,最后到达最右端$m$,求最小路程。出租车只能一次载一只牛。

https://www.cnblogs.com/five20/p/9055809.html

贪心。答案=$sum_{i=1}^{n} |a_i-b_i|$+空车行驶距离。

只需考虑空车行驶距离最小。

 

(图片来自上面链接)

由手模过程,我们可以知道:每次选择距离最小的$(t_i,s_j)$,将答案累加。因为还要计算从起点到最近的$s$,终点到最近的$t$的距离,所以把$0$加入$t$,把$m$加入$s$。

然后把$s$,$t$分别从小到大排序,求$sum_{i=1}^{n+1}|s_i-t_i|$即可。

从这题出发,遇到贪心题,先分解答案,分出变量和不变量,然后考虑不变量的最小值。平时练习时,需要记住典型的贪心。

原文地址:https://www.cnblogs.com/xzs123456/p/12290357.html