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;
}