P5017 [NOIP2018 普及组] 摆渡车

思路：

考虑动态规划。

定义 \(dp_i\) 表示若有一班车在第 \(i\) 个时间出发所有人等待的时间，则状态转移方程为：

\[dp_i = dp_j + \operatorname{get}(j+1,i)(j \le i – m) \]

其中 \(\operatorname{get}(l,r)\) 表示等车时间在 \([l,r]\) 范围内的人在 \(r\) 处上车的等待时间，考虑 \(O(1)\) 求出 \(\operatorname{get}(l,r)\)。

定义 \(s_i\) 表示等车时间在 \([0,i]\) 的所有人的等车时间之和，\(a_i\) 表示等车时间在 \([0,i]\) 的人的个数，则：

\[\operatorname{get}(l,r) = r \times (a_r – a_{l-1}) – (s_r – s_{l-1}) \]

此时时间复杂度优化到了 \(O(T^2)\)，考虑缩小 \(j\) 的范围。

注意到若在某时刻回来，且等待不发车时间 \(>m\) 了，肯定没有中间发一次车优，则 \(j\) 的范围应该在 \([i-2m,i-m]\)。

此时时间复杂度为 \(O(TM)\)。

完整代码：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=4e6+10; 
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,x,k,ans=1e18;
ll a[N],s[N],dp[N];
ll get(ll l,ll r){
	if(l>r)
	  return 0;
	if(!l)
	  return r*a[r]-s[r];
	return r*(a[r]-a[l-1])-(s[r]-s[l-1]); 
}
bool End;
int main(){
	memset(dp,0x7f,sizeof(dp));
	n=read(),m=read();
	while(n--){
		x=read();
		a[x]++;
		k=max(k,x);
	}
	for(ll i=1;i<N;i++){
		s[i]=s[i-1]+a[i]*i;
		a[i]+=a[i-1];
	}
	for(int i=0;i<m;i++)
	  dp[i]=get(0,i);
	for(int i=m;i<=k+m;i++)
	  for(int j=max(0ll,i-2ll*m);j<=i-m;j++)
		dp[i]=min(dp[i],dp[j]+get(j+1,i));
	for(int i=k;i<=k+m;i++)
	  ans=min(ans,dp[i]);
	write(ans); 
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}