A37440. 月球疏散行动
题目描述
月球疏散行动
题目描述：
为了避免太阳爆发引起的灾难，人类决定给地球装上发动机，最终逃离太阳系。原计划要带着月球一起走，结果月球行星发动机发生灾难性故障，必须炸毁月球。为此，在月球上的工作人员都要疏散回地球。
月球基地有一艘太空穿梭机可以用来疏散工作人员。但是人们分散在各处，必须前往基地集合，他们到达基地的时间不等。穿梭机可以将抵达基地等待登机的工作人员先送回地球，然后再返回基地疏散下一批工作人员。
总共有N名工作人员需要疏散，太空穿梭机从月球到地球往返一次花时间M小时，第i个人抵达基地等待登机的时刻为Ti。
指挥官希望所有工作人员在基地等待的时间总和最小，而且他可以任意安排穿梭机的起飞时间，假定穿梭机足够大，可以装下所有工作人员，在不计登机和下机时间等因素的情况下，最小的等候时间总和是多少？
例如：N=5，M=4，1号~5号工作人员到达基地的时刻依次为11、3、3、5、10，
穿梭机可以在3时出发，先送2号、3号工作人员去地球，然后于7时返回月球基地；
此时，4号工作人员已于5时到达基地，等候了2小时。这时让穿梭机马上送走他，然后于11时从地球返回基地；
此时，5号工作人员已于10时到达基地，等候了1小时；
而1号工作人员刚好于11时到达基地，等候0小时；
穿梭机于11时将两人送走，即完成全部疏散任务。总的等候时间=4号工作人员等候时间+5号工作人员等候时间=2+1=3小时。
无法再找到有更小等候时间总和的方案。
输入描述
第一行输入两个正整数N（1≤N≤500），M（1≤M≤100），以一个空格隔开，分别表示工作人员人数和穿梭机的往返时间
第二行输入N个正整数，依次表示某个工作人员到达基地等候登机的时刻Ti（1≤Ti≤4000000），相邻两数之间用一个空格隔开
输出描述
输出一个整数，表示所有工作人员等候时间之和的最小值（单位：小时）
样例输入
5 4
11 3 3 5 10
样例输出
3
参考答案
#include <iostream>
using namespace std;
const int N=4e6+105;
int cnt[N],sum[N],f[N];
int main()
{
int n,m,maxn=-1,t;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>t;
cnt[t]++;//在t时刻等车的人数+1
sum[t]+=t;//在t时刻等车的人的总等车时间和
maxn=max(maxn,t);//最晚到车站的时间点
}
//完成数组前缀合
for(int i=1;i<maxn+m;i++){//maxn+m-1 列车最晚到车站的时间
cnt[i]+=cnt[i-1];//在i时刻等车人数前缀和
sum[i]+=sum[i-1];//在i时刻等车时间前缀和
}
for(int i=1;i<maxn+m;i++){//i枚举区间右端点
//f[i]表示前i个点最后一个区间右边界是i,所有点到各自区间的右边界的距离之和值最小
if(i>=m && cnt[i]==cnt[i-m]){//数据优化这段时间没有人等待
f[i]=f[i-m];continue;
}
f[i]=i*cnt[i]-sum[i];//初始化f[i] 区间[0,i]
for(int j=max(0,i-2*m+1);j<=i-m;j++)//j枚举区间左端点 max(0,i-2*m+1)优化左端点
f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
}
int ans=1e9;
for(int i=maxn;i<maxn+m;i++)
ans=min(ans,f[i]);
cout<<ans;
return 0;
}