[NOIP2018]摆渡车

NC21471. [NOIP2018]摆渡车

描述

有 n 名同学要乘坐摆渡车从人大附中前往人民大学，第 i 位同学在第 t_i 分钟去

等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学)，这样往返一趟总共花费 m 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。
凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢?
注意:摆渡车回到人大附中后可以即刻出发。

输入描述

第一行包含两个正整数n，m，以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。
第二行包含 n 个正整数，相邻两数之间以一个空格分隔，第 i 个非负整数 t_i 代表第 i 个同学到达车站的时刻。

输出描述

输出一行，一个整数，表示所有同学等车时间之和的最小值(单位:分钟)。

示例1

输入:

5 1
3 4 4 3 5

输出:

说明:

同学 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

输出:

说明:

同学 3 在第 1 分钟开始等车，等待 0 分钟，在第 1 分钟乘坐摆渡车出发。摆渡车在第 6 分钟回到人大附中。
同学 4 和同学 5 在第 5 分钟开始等车，等待 1 分钟，在第 6 分钟乘坐摆渡车出发。摆渡车在第 11 分钟回到人大附中。
同学 1 在第 11 分钟开始等车，等待 2 分钟;同学 2 在第 13 分钟开始等车，等待 0 分钟。他/她们在第 13 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 4。可以证明，没有总等待时间小于 4 的方案。

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 274ms, 内存消耗: 110960K, 提交时间: 2022-02-01 14:13:39

n, m = map(int, input().split())
t = list(map(int, input().split()))
mt = max(t)
c, s, f = [0] * (mt + m), [0] * (mt + m), [0] * (m + mt)
for x in t:
	c[x] += 1; s[x] += x
for i in range(1, len(c)):
	c[i] += c[i - 1]; s[i] += s[i - 1]

ans = int(1e18)

for i in range(len(c)):
	if i >= m and c[i] == c[i - m]:
		f[i] = f[i - m]
		continue
	f[i] = c[i] * i - s[i]
	for j in range(max(i - 2 * m + 1, 0), i - m + 1):
		f[i] = min(f[i], f[j] + (c[i] - c[j]) * i - (s[i] - s[j]))
	if i >= mt: ans = min(ans, f[i])

print(ans)

C++ 解法, 执行用时: 30ms, 内存消耗: 908K, 提交时间: 2021-10-20 20:50:04

#include <bits/stdc++.h>
using namespace std;

int n,m,i,j,k,ans=0x7f7f7f7f,t[505],dp[505][205];

int main(){
	memset(dp,0x7f,sizeof(dp));
	cin >> n >> m;
	for(i=0;i<205;i++) dp[1][i]=i;
	for(i=1;i<=n;i++) cin >> t[i];
	sort(t+1,t+n+1);
	for(i=1;i<=n;i++){
		for(j=0;j<2*m;j++){
			for(k=0;k<2*m;k++){
				if(t[i-1]+k == t[i]+j || t[i-1]+k+m<=t[i]+j)
					dp[i][j]=min(dp[i][j],dp[i-1][k]+j);
			}
		}
	}
	for(i=0;i<2*m;i++) ans=min(ans,dp[n][i]);
	cout << ans << endl;
	return 0; 
}