题解：P5017 [NOIP2018 普及组] 摆渡车

这道题乍一看，很多人（包括我）就会想到贪心。

但是我们仔细想一下，正着贪心（也就是摆渡车能开就开）这个是不行的。那倒着贪心呢（也就是让最后一个人不等待，然后一直往前推 \(m\) 时刻）？也不行，这里有一个反例。

4 5
1 1 1 5

正确输出

1

第二种贪心方式的输出

12

所以我们用到了 DP，状态设计起来还是比较简单的。

我们令 \(t\) 为上一次摆渡车开走的时间，摆渡车没有开走过 \(t\) 就等于 \(1\)。再令 \(f_i\) 表示在 \(i\) 时刻摆渡车开走了，\(t \sim i\) 时刻的同学的等待时间。

那么转移为 $$f_i \gets min_{t\le i-m}(f_i,f_t+[t+1]\sim i)$$。

AC code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n, m, t[N], dp[N], s1[N], s2[N], cnt[N];
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &t[i]);t[i] += 1;}sort(t + 1, t + n + 1);for (int i = 1; i <= n; i++)if (t[i] - t[i - 1] >= 2 * m) {int c = t[i] - t[i - 1] - 2 * m;for (int j = i; j <= n; j++)t[j] -= c;}int T = t[n] + m;for (int i = 1; i <= n; i++)cnt[t[i]]++;for (int i = 1; i <= T; i++) {s1[i] = s1[i - 1] + cnt[i];s2[i] = s2[i - 1] + i * cnt[i];}int ans = 1 << 30;for (int i = 1; i <= T; i++) {dp[i] = i * s1[i] - s2[i];for (int j = i - m; j >= 1 && j >= i - 2 * m + 1; j--)dp[i] = min(dp[i], dp[j] + i * (s1[i] - s1[j]) - (s2[i] - s2[j]));if (i >= t[n])ans = min(ans, dp[i]);}printf("%d", ans);
}