感谢\(xjk\)大佬推荐的好题
这里只说前半部分的转化，后半部分直接暴力\(dp\)+斜率优化即可
我们考虑如何朴素\(dp\)，我们发现一个猫的要求时间是他结束游玩的时间\(-\)他所在的位置，及\(T_i - D_{H_i}\)
我们把猫咪按照\(T_i - D_{H_i}\)从小到大排序，可以发现放置一个铲屎官就是把前缀一些未取到的猫咪取走，而产生的贡献即为这些猫咪到铲屎官的距离
因此原问题就变成了把猫咪分成若干段，使得对于每段内所有猫咪距离这段右端点的距离之和的最大值最小
直接\(dp\)即可
最终复杂度\(O(np)\)
标签：猫咪,距离,Cats,CF311B,Transport,dp From： https://www.cnblogs.com/fox-konata/p/17720921.html