[USACO08NOV] Time Management S

题意

有 N 个工作。第 i 个工作需要 T_i 时间完成，并且必须在时刻 S_i 或之前完成。

工作一旦开始就必须连续做完，不能中断。要求求出最晚可以从什么时候开始工作，使得所有工作都能按时完成。如果从 0 开始也无法完成，输出 -1。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
45
46
47
48
49
50
51
52
53#include <bits/stdc++.h>
using namespace std;

struct Job {
    int t;
    int s;
};

int n;
Job job[10];
bool used[10];

bool dfs(int done, int now) {
    if (done == n) return true;

    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        int finishTime = now + job[i].t;
        if (finishTime > job[i].s) continue;

        used[i] = true;
        if (dfs(done + 1, finishTime)) return true;
        used[i] = false;
    }
    return false;
}

bool canStart(int startTime) {
    memset(used, 0, sizeof(used));
    return dfs(0, startTime);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    int maxS = 0;
    for (int i = 1; i <= n; i++) {
        cin >> job[i].t >> job[i].s;
        maxS = max(maxS, job[i].s);
    }

    for (int startTime = maxS; startTime >= 0; startTime--) {
        if (canStart(startTime)) {
            cout << startTime << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

朴素解枚举开始时间，并用 DFS 尝试所有任务顺序。它适合小数据验证，但 N 最大是 1000，不能枚举排列。

这题可以反过来想：既然要求“最迟开始”，那就从最后往前安排任务。

截止时间越晚的任务越适合放在后面。于是把所有任务按截止时间 S 从大到小排序，然后倒推：

text

1
2当前任务最晚完成时间 = min(后面任务留出的时间, 当前任务截止时间)
当前任务最晚开始时间 = 当前任务最晚完成时间 - 当前任务耗时

处理完所有任务后，得到的时间就是整套任务最晚可以开始的时间。

样例倒推过程

样例任务按截止时间从大到小排序：

任务耗时 `T`	截止时间 `S`	处理前 `now`	处理后 `now`
`5`	`20`	`20`	`15`
`1`	`16`	`15`	`14`
`8`	`14`	`14`	`6`
`3`	`5`	`6`	`2`

最后得到 2，表示最迟从时刻 2 开始。

这里读表时要注意：表格是从后往前安排任务。真正正向执行时，顺序会反过来。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

struct Job {
    int t;
    int s;
};

Job job[1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> job[i].t >> job[i].s;
    }

    sort(job + 1, job + n + 1, [](const Job &a, const Job &b) {
        return a.s > b.s;
    });

    int now = job[1].s;
    for (int i = 1; i <= n; i++) {
        // 当前任务必须不晚于自己的截止时间完成，也不能晚于后面任务留出的时间。
        if (now > job[i].s) now = job[i].s;
        now -= job[i].t;
    }

    if (now < 0) {
        cout << -1 << '\n';
    } else {
        cout << now << '\n';
    }

    return 0;
}

复杂度

排序任务需要 $O(N log N)$ 。
倒推扫描一次需要 $O(N)$ 。
总时间复杂度 $O(N log N)$ 。
空间复杂度 $O(N)$ 。

总结

这题虽然在二分训练单里，但最直接的做法是排序贪心。

“最迟开始”适合反向考虑：先把后面的任务尽量贴近截止时间，再一步步往前推。只要最终时间不小于 0，它就是答案；否则说明所有任务从 0 开始也无法按时完成。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。