题解 | #[NOIP2018]摆渡车#

#include<iostream>
using namespace std;

const int MAXT = 4000105;
int t[MAXT],cnt[MAXT],sum[MAXT],dp[MAXT];
int main() {
	int n,m,last_one=0;
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		int a;
		cin>>a;
		t[a]++;
		last_one = max(last_one,a);
	}
	cnt[0] = t[0];
	sum[0] = 0;
	for(int i = 1; i < last_one + m; i++){
		cnt[i] = cnt[i - 1] + t[i];
		sum[i] = sum[i - 1] + i * t[i];
	}
	for(int i = 0; i < last_one + m; i++){
		if(i <m){
			dp[i] = cnt[i] * i - sum[i];	
		}else if(cnt[i] == cnt[i - m]){
			dp[i] = dp[i - m];
		}else{
			dp[i] = 0x3f3f3f3f;
			for(int j = max(0, i-2*m+1); j<=i-m; j++){
				dp[i] = min(dp[i], dp[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
			}
		}
	}
    int ans=0x3f3f3f3f;
	for(int i = last_one; i < last_one + m; i++){
		ans = min(ans, dp[i]);
	}
	cout<<ans;
	return 0;
}