摆渡车

Posted on Edited on In Word count in article: 453 Reading time ≈ 2 mins.
摆渡车

摆渡车

题意

你可以操控一辆车的发车时间，你也知道跑一次往返的时间，你还知道每一个人到达车站的时间

让你找到一种方案使得所有人的等待时间之和最少，求这个最小时间

分析

第一反应是把到达车站的人作为一个整体 然后我们可以枚举最近的一次发车时间

假设现在的时间是\(\text{i}\)，最近的一次发车时间是\(\text{j}\) 那么从\(j\sim i\)的等待时间可以表示为\(\sum_{j<t_x\le i}i-t_x\) 那么我们把这个拆开来看 \[ \begin{align*} \sum_{j<t_x\le i}i-t&=\sum_{j<t_x\le i}i-\sum_{j < t_x\le i}t_x\\ &=(cnt_i-cnt_j)*i-(sum_i-sumj) \end{align*} \]

貌似变得友好了呢

直观感觉一下，我们有效的最近的发车时间应该是不能小于(\(\text{i-m}\))的

那么其实就是有一部分人在上一次发车时就开始等待了 那么这个也是要加入贡献的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 5e6;

int n, m, t, mt, ans(0x7fffffff);
int cnt[maxn], sum[maxn], f[maxn];

inline int Read()
{
    int x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline int wait(int l, int r)
{
    return (cnt[r] - cnt[l]) * r - (sum[r] - sum[l]);
}

int main()
{
    n = Read(), m = Read();
    for (int i = 1; i <= n; ++i) {
        mt = max(t = Read(), mt);
        cnt[t]++, sum[t] += t;
    }
    for (int i = 1; i < m + mt; ++i) cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
    for (int i = 0; i < m + mt; ++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(i - 2 * m + 1, 0); j <= i - m; ++j)
            f[i] = min(f[i], f[j] + wait(j, i));
        if (i >= mt) ans = min(ans, f[i]);
    }
    printf ("%d\n", ans);
}