NOIP2018 普及组 T3 摆渡车

文章目录

题目传送门
算法解析
总代码
提交记录
尾声

题目传送门

洛谷 P5017 [NOIP2018 普及组] 摆渡车

算法解析

本题是一道 $D P$ 题。

我们可以把时间想成一个数轴，这样每趟车就是一个区间（到达时间到离开时间）。

定义 $f_i$ 表示前 $i$ 个点，最后一个区间右边界是 $i$ ，所有点到各自区间的右边界的距离之和的最小值。

这样的话，状态转移方程为：

$f_i = min(f_j + \sum^{}_{j < t_k \leq i}{i-t_k}$ $\leq i))$

但是枚举所有的 $k$ 肯定是不行的 QWQ，所以我们要做一个前缀和，即：

$cnt_i$ 表示前 $i$ 个时间点要上车的人数， $sum_i$ 表示前 $i$ 个时间点要上车的人的到达车站时间之和。

于是，状态转移方程变为：

$f_i = min(f_j + (cnt_i - cnt_j) \cdot i - (sum_i - sum_j))$

这样，我们就可以得出代码：

#include <cstdio>
using namespace std;

const int N = 4e6 + 105;

int n, m;
int t;
int cnt[N];
int sum[N];
int maxt;
int f[N];
int ans;

void bemin(int &a, int b) {
	a = a < b ? a : b;
}

void bemax(int &a, int b) {
	a = a > b ? a : b;
}

void inp() {
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &t);
		++cnt[t];
		sum[t] += t;
		bemax(maxt, t);
	}
}

void work() {
	for(int i = 1; i < maxt + m; ++i) {
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	
	for(int i = 1; i < maxt + m; ++i) {
		f[i] = cnt[i] * i - sum[i];
		for(int j = 0; j <= i - m; ++j)
			bemin(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
	}
	
	ans = 1e9;
	
	for(int i = maxt;  i < maxt + m; ++i)
		bemin(ans, f[i]);
	
	printf("%d\n", ans);
}

int main() {
	inp();
	work();
	
	return 0;
}

但是只能拿到 50 分 QWQ。

我们发现直接在 $\cdot m + 1$ 的位置就可以安排一趟车，小于它的也只能更大，所以可以改为：

for(int j = max(0, i - 2 * m + 1); j <= i - m; ++j)

还有就是如果没有人等待，那么这趟车就肯定不能发对吧，所以可以加个优化：

if(i >= m && cnt[i] == cnt[i - m]) {
	f[i] = f[i - m];
	continue;
}

这样这道题就 A 了

总代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 4e6 + 105;

int n, m;
int t;
int cnt[N];
int sum[N];
int maxt;
int f[N];
int ans;

void bemin(int &a, int b) {
	a = a < b ? a : b;
}

void bemax(int &a, int b) {
	a = a > b ? a : b;
}

void inp() {
	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &t);
		++cnt[t];
		sum[t] += t;
		bemax(maxt, t);
	}
}

void work() {
	for(int i = 1; i < maxt + m; ++i) {
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	
	for(int i = 1; i < maxt + m; ++i) {
		if(i >= m && cnt[i] == cnt[i - m]) {
			f[i] = f[i - m];
			continue;
		}
		
		f[i] = cnt[i] * i - sum[i];
		for(int j = max(0, i - 2 * m + 1); j <= i - m; ++j)
			bemin(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
	}
	
	ans = 1e9;
	
	for(int i = maxt;  i < maxt + m; ++i)
		bemin(ans, f[i]);
	
	printf("%d\n", ans);
}

int main() {
	inp();
	work();
	
	return 0;
}