题解 | #[NOIP2018]摆渡车#

观察到$tt$很小，于是考虑在时间轴上$dpdp$。

设$c[i]c[i]$为在$ii$时刻出发的人数。

设$dp[i]dp[i]$是在$ii$时刻出发，前$ii$分钟等待时间最少的值。

所以

$dp[i]={}_{j=1}^{i-m}dp[j]+{\sum }_{k=j+1}^i(i-k)\ast c[k]dp[i]=\; \backslash min\_\{j=1\}^\{i-m\}\; dp[j]+\; \backslash sum\_\{k=j+1\}^\{i\}(i-k)*c[k]$

单独看后面那一坨东西：

${\sum }_{k=j+1}^i(i-k)\ast c[k]\backslash sum\_\{k=j+1\}^\{i\}(i-k)*c[k]$

$={\sum }_{k=j+1}^{i}i\ast c[k]-k\ast c[k]=\backslash sum\_\{k=j+1\}^\{i\}i*c[k]-k*c[k]$

然后弄一个$cc$的前缀和$aa$和$c[i]\ast ic[i]*i$的前缀和$b[i]b[i]$。

于是变成

$i\ast (a[i]-a[j])-(b[i]-b[j])i*(a[i]-a[j])-(b[i]-b[j])$

代回去：

$dp[i]={}_{j=1}^{i-m}dp[j]+i\ast (a[i]-a[j])-(b[i]-b[j])dp[i]=\; \backslash min\_\{j=1\}^\{i-m\}\; dp[j]+i*(a[i]-a[j])-(b[i]-b[j])$

然后50pts

拆。

$dp[i]=dp[j]+i\ast a[i]-i\ast a[j]-b[i]+b[j]dp[i]=dp[j]+i*a[i]-i*a[j]-b[i]+b[j]$

$i\ast a[j]+dp[i]-i\ast a[i]+b[i]=dp[j]+b[j]i*a[j]+dp[i]-i*a[i]+b[i]=dp[j]+b[j]$

然后设$x=a[j],y=dp[j]+b[j]x=a[j],y=dp[j]+b[j]$

于是就是一条斜率为$ii$的直线。

然后$ii$显然单调递增。

好了。斜率优化。

using namespace std;
#define ll int
#define f(i,a,b) for(ll i=a;i<=b;i++)
inline ll rd() {
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
#define d rd()
#define pb push_back
const ll N=300010;
struct edge{ll v,w,nx;}e[N<<1];
ll hd[N],cnt;
void add(ll u,ll v,ll w){e[++cnt]=(edge){v,w,hd[u]};hd[u]=cnt;}
ll qp(ll a,ll b,ll p){
	ll ans=1;while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;b>>=1;
	}return ans;
}ll n,m;
ll c[4100010];
ll dp[4100010];
ll a[4100010],b[4100010];
ll mx,ans=1000000000;
double sl(ll i,ll j){
	double xone=a[i],xtwo=a[j];
	double yone=dp[i]+b[i];
	double ytwo=dp[j]+b[j];
	return (ytwo-yone)/((xone==xtwo)?1e-9:xtwo-xone);
}ll q[4100010],h,t;
int main(){
	n=d,m=d;f(i,1,n){ll x=d;a[x]++,b[x]+=x;mx=max(mx,x);}
	n=mx+m-1;f(i,1,n)a[i]+=a[i-1],b[i]+=b[i-1];
	h=1,t=0;
	f(i,0,n){if(i-m>=0){while(h<t&&sl(q[t-1],q[t])>=sl(q[t],i-m))t--;q[++t]=i-m;}
		while(h<t&&sl(q[h],q[h+1])<=(double)i)h++;
		ll j=q[h];dp[i]=i*a[i]-b[i];
		if(h<=t)dp[i]=min(dp[i],dp[j]+i*(a[i]-a[j])-(b[i]-b[j]));
	}f(i,mx,n)ans=min(ans,dp[i]);
	printf("%d",ans);
	return 0;
}