Fork me on GitHub

贪心算法-任务调度问题

发表于 | 分类于 | | 次阅读
一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集 S 。关于S 的一个时间表用于描述S 中单位时间任务的执行次序。时间表中第 1 个任务从时间 0 开始执行直至时间 1 结束，第 2 个任务从时间 1 开始执行至时间 2 结束，…，第n个任务从时间 n-1 开始执行直至时间 n 结束。具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下：(1) n 个单位时间任务的集合 S = {1,2,…,n}（n ≤ 500）；(2) 任务i的截止时间 d[i], 1 ≤ i ≤ n, 1 ≤ d[i] ≤ n，即要求任务 i 在时间 d[i] 之前结束；(3) 任务 i 的误时惩罚 1 ≤ w[i] ≤ 1000, 1 ≤ i ≤ n, 即任务 i 未在时间 d[i] 之前结束将招致 w[i] 的惩罚；若按时完成则无惩罚。任务时间表问题要求确定 S 的一个时间表（最优时间表）使得总误时惩罚达到最小。

Problem E.任务调度问题

时间限制 1000 ms
内存限制 128 MB

题目描述

一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集 S 。关于S 的一个时间表用于描述S 中单位时间任务的执行次序。时间表中第 1 个任务从时间 0 开始执行直至时间 1 结束，第 2 个任务从时间 1 开始执行至时间 2 结束，…，第n个任务从时间 n-1 开始执行直至时间 n 结束。具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下：
(1) n 个单位时间任务的集合 S = {1,2,…,n}（n ≤ 500）；
(2) 任务i的截止时间 d[i], 1 ≤ i ≤ n, 1 ≤ d[i] ≤ n，即要求任务 i 在时间 d[i] 之前结束；
(3) 任务 i 的误时惩罚 1 ≤ w[i] ≤ 1000, 1 ≤ i ≤ n, 即任务 i 未在时间 d[i] 之前结束将招致 w[i] 的惩罚；若按时完成则无惩罚。
任务时间表问题要求确定 S 的一个时间表（最优时间表）使得总误时惩罚达到最小。

输入数据

第一行是正整数 n ，表示任务数。接下来的 2 行中，每行有 n 个正整数，分别表示各任务的截止时间和误时惩罚。

输出数据

将计算出的最小总误时惩罚输出。

样例输入

1
2
3
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

样例输出

1
50

题解

这道题目类似于活动安排问题。首先将所有任务按照误时惩罚从大到小排序，然后依次从左到右遍历每个任务，将其安排在离截止时间点最近的（包括截止时间点处）未安排任务的时间点处完成，若无法找到这个时间点，则这个任务无法按时完成，将其误时惩罚加到总误时惩罚中。这样得到的总误时惩罚是最小的。

AC代码

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int n, d[510], w[510], visit[510];
int i, j;
long long result;

int main() {
    memset(visit, 0, sizeof(visit));
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> d[i];
    }
    for (i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (i = 0; i < n; i++) {
        for (j = 1; j < n; j++) {
            if (w[j] < w[j + 1]) {
                swap(d[j], d[j + 1]);
                swap(w[j], w[j + 1]);
            }
        }
    }
    for (i = 1; i <= n; i++) {
        bool flag = false;
        for (j = d[i]; j > 0; j--) {
            if (!visit[j]) {
                visit[j] = 1;
                flag = true;
                break;
            }
        }
        if (!flag) {
            result += w[i];
        }
    }
    cout << result << endl;
    return 0;
}
0%