题意

安排摆渡车出发的时间，使这些同学的等车时间之和最小。

分析

 一

根据题意我们就有如下转移式子，令 $f_i$ 是以时间点 $i$ 为结尾的最小等车时间。那么 
这样的时间复杂度为 $O(t^3)$ 必须优化。

 二

考虑前缀和优化，令 $sum_i$ 为从 $1$ 到 $i$ 的总时间是多少， $cnt_i$ 为从 $1$ 到 $i$ 有多少个人，那么转移方程优化为
$$f_i = \min_{j\le i-m}\lbrace f_j+(cnt_i-cnt_j)\times i+sum_j-sum_i \rbrace$$
这样时间复杂度为 $O(t^2)$ 。还是要考虑优化。

 三

考虑到 $cnt_i,sum_i$ 都是常数项，考虑斜率优化 $dp$ 。令 $j<i$ 。现在考虑 $i$ 的转移，如果决策点 $j$ 是 $i$ 的最优决策点，则有
$$f_i =  f_j+(cnt_i-cnt_j)\times i+sum_j-sum_i $$
$$cnt_j\times i+f_i+sum_i-cnt_i\times i = f_j$$
发现，如果要让 $f_i$ 最小，那么就要使该一次函数的截距最小。那么维护一个下凸壳，就可以了。那么如果 $k,j$ 是 $i$ 的决策点，化简之后得到下式。 
$$\frac{f_j+sum_j-f_k-sum_k}{cnt_j-cnt_k}\le i(k<j)$$ 

 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e7+100;
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f?-x:x;
}
int cnt[N],sum[N],n,m,f[N];
int Q[N],l,r,Max;
double K(int y,int x) {
	if(cnt[x] == cnt[y]) return 1e9*((f[x]+sum[x]-f[y]-sum[y]));
	else return (double) (f[x]+sum[x]-f[y]-sum[y])/(cnt[x] - cnt[y]);
}
int main()
{
	n = read();m = read();
	for(int i = 1;i <= n;i++) {
		int x = read();Max = max(Max,x);
		cnt[x]++;sum[x] += x;
	}
	for(int i = 1;i < Max + m;i++) cnt[i] += cnt[i-1],sum[i] += sum[i-1];
	l = 1;r = 0;
	for(int i = 0;i < Max + m;i++){
		if(i - m >= 0) {
			while(l < r && K(Q[r-1],Q[r]) - K(Q[r],i-m) >= 0) r--;
			Q[++r] = i - m;
		}
		while(l < r && K(Q[l],Q[l+1]) - i <= 0) l++;
		f[i] = cnt[i] * i - sum[i];
		if(l <= r) f[i] = min(f[i],f[Q[l]]+(cnt[i]-cnt[Q[l]])*i-sum[i]+sum[Q[l]]);
	}
	int ans = 0x3f3f3f3f;
	for(int i = Max;i < Max + m;i++) ans = min(ans,f[i]);
	cout << ans << endl;
	return 0;
}