题目描述
有 ? 名同学要乘坐摆渡车从人大附中前往人民大学,第 ? 位同学在第 ?? 分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费 ? 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。
凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?
注意:摆渡车回到人大附中后可以即刻出发。
输入
输入文件名为 bus.in。
第一行包含两个正整数 ?,m,以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。
第二行包含 ? 个正整数,相邻两数之间以一个空格分隔,第 i 个非负整数 ?? 代表第 i 个同学到达车站的时刻。
输出
输出文件名为 bus.out。
输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。
样例输入1
5 1
3 4 4 3 5
样例输出1
0
【输入输出样例 1 说明】
同学 1 和同学 4 在第 3 分钟开始等车,等待 0 分钟,在第 3 分钟乘坐摆渡车出发。摆渡车在第 4 分钟回到人大附中。
同学 2 和同学 3 在第 4 分钟开始等车,等待 0 分钟,在第 4 分钟乘坐摆渡车出发。摆渡车在第 5 分钟回到人大附中。
同学 5 在第 5 分钟开始等车,等待 0 分钟,在第 5 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 0。
样例输入2
5 5
11 13 1 5 5
样例输出2
4
【输入输出样例 2 说明】
同学 3 在第 1 分钟开始等车,等待 0 分钟,在第 1 分钟乘坐摆渡车出发。摆渡车在第 6 分钟回到人大附中。
同学 4 和同学 5 在第 5 分钟开始等车,等待 1 分钟,在第 6 分钟乘坐摆渡车出发。摆渡车在第 11 分钟回到人大附中。
同学 1 在第 11 分钟开始等车,等待 2 分钟;同学 2 在第 13 分钟开始等车,等待 0 分钟。他/她们在第 13 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。
总等待时间为 4。可以证明,没有总等待时间小于 4 的方案。
数据范围限制
对于 10% 的数据,n ≤ 10 , m = 1 , 0 ≤ t i ≤ 100 n ≤ 10,m = 1, 0 ≤ t_i ≤ 100n≤10,m=1,0≤ti≤100。
对于 30% 的数据,n ≤ 20 , m ≤ 2 , 0 ≤ t i ≤ 100 n ≤ 20, m≤ 2, 0 ≤ t_i≤ 100n≤20,m≤2,0≤ti≤100。
对于 50% 的数据,n ≤ 500 , m ≤ 100 , 0 ≤ t i ≤ 1 0 4 n ≤ 500, m ≤ 100, 0 ≤ t_i ≤ 10^4n≤500,m≤100,0≤ti≤104。
另有 20% 的数据,n ≤ 500 , m ≤ 10 , 0 ≤ t i ≤ 4 × 1 0 6 n ≤ 500, m≤ 10, 0 ≤ t_i ≤ 4 × 10^6n≤500,m≤10,0≤ti≤4×106。
对于 100% 的数据,n ≤ 500 , m ≤ 100 , 0 ≤ t i ≤ 4 × 1 0 6 n ≤ 500, m ≤ 100, 0 ≤ t_i ≤ 4 × 10^6n≤500,m≤100,0≤ti≤4×106。
题解&思路
本题采取动态规划的方法实现。
我们设 f i f_ifi 表示第 i ii 分钟同学的最小等车时间
我们考虑如何转移
我们可以枚举一个 j jj ,使得 j jj 之前的已经全部过河,现在后面的在 i ii 时刻过河。
设 S i S_iSi 表示 i ii 时刻之前 t tt 的总和,C i C_iCi 表示 i ii 时刻之前有多少个人到车站。
那么转移方程是:
f i = m i n ( f j + i ( C i − C j ) − ( S i − S j ) ) f_i=min(f_j+i(C_i-C_j)-(S_i-S_j))fi=min(fj+i(Ci−Cj)−(Si−Sj))
但是,我们注意到 0 ≤ t i ≤ 4 × 1 0 6 0 ≤ t_i ≤ 4 × 10^60≤ti≤4×106,这样的时间复杂度只能过掉50分的数据,我们想想怎么优化?
很明显,我们需要用斜率优化
若 j jj 比 k kk 优,则
f j + i ( C i − C j ) + ( S i − S j ) < f k + i ( C i − C k ) − ( S i − S k ) f_j+i(C_i-C_j)+(S_i-S_j)<f_k+i(C_i-C_k)-(S_i-S_k)fj+i(Ci−Cj)+(Si−Sj)<fk+i(Ci−Ck)−(Si−Sk)
最终优化为:
( f j + S j ) − ( f k + S k ) C j − C k < i \frac{(f_j+S_j)-(f_k+S_k)}{C_j-C_k}<iCj−Ck(fj+Sj)−(fk+Sk)<i
则对于一个点 i ii ,它在平面上的坐标为 ( C i , F i + S i ) (C_i,F_i+S_i)(Ci,Fi+Si)
然后我们就可以用单调队列去愉快地维护下凸包了。
C o d e CodeCode
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int N=505;
int n,m,h,t;
ll ans,mn=1e18,sum;
ll ti[N],s[5000005],f[5000005],c[5000005],d[5000005];
double X(int x){
return c[x];
}
double Y(int x){
return (double)(f[x]+s[x]);
}
double slope(int i,int j){
if (X(i)==X(j)) return (double)((Y(j)-Y(i))/(1e-18));//important
return (Y(j)-Y(i))/(X(j)-X(i));
}
int main(){
//freopen("bus.in","r",stdin);
//freopen("bus.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%lld",&ti[i]);
s[ti[i]]+=ti[i];
c[ti[i]]++;
mn=min(mn,ti[i]);
sum=max(sum,ti[i]);
}
for (int i=0;i<sum+m;i++)
c[i]+=c[i-1],s[i]+=s[i-1];
ans=1e18;
f[mn]=0;
h=1;t=0;
for(int i=mn+1;i<sum+m;i++){
if(i-m>=0){
while(h<t&&slope(d[t-1],d[t])>=slope(d[t-1],i-m)) --t;
d[++t]=i-m;
}
while(h<t&&slope(d[h],d[h+1])<=i) ++h;
int j=d[h];
if(h<=t) f[i]=f[j]+(c[i]-c[j])*i-(s[i]-s[j]);
else f[i]=c[i]*i-s[i];
if (i>=sum)
ans=min(ans,f[i]);
}
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}