P1065. 作业调度方案

发表于 分类于 阅读次数： Waline： 本文字数： 457 阅读时长 ≈ 2 分钟

考点

  • 模拟

题解

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>

using namespace std;

const static int N = 1e5 + 10;

//m为机器数，n为工件数
int m, n;

//记录每个机器的时间轴
bool machine_timeline[30][N];

//记录当前工件的工序状态
int project_record[30];

//记录任务执行顺序
int project_list[550];

//每个工件的上一次的最长耗时线
int project_timeline[30];

//记录工件号及其工序指定的机器与时间开销
//first为指定的机器号，second为时间开销
pair<int, int> project_table[30][30];

void read()
{
    cin >> m >> n;
    for (int i = 1; i <= m * n; ++i)
    {
        cin >> project_list[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> project_table[i][j].first;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> project_table[i][j].second;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    read();
    int ans = 0, cost = 0, project_id, machine_id, machine_cost;
    for (int i = 1; i <= m * n; ++i)
    {
        project_id = project_list[i], ++project_record[project_id];
        machine_id = project_table[project_id][project_record[project_id]].first;
        machine_cost = project_table[project_id][project_record[project_id]].second;
        cost = 0;
        for (int j = project_timeline[project_id] + 1;; ++j)
        {
            if (!machine_timeline[machine_id][j])
            {
                ++cost;
            }
            else
            {
                cost = 0;
            }
            if (cost == machine_cost)
            {
                for (int k = j; k > j - machine_cost; --k)
                {
                    machine_timeline[machine_id][k] = true;
                }
                ans = max(ans, j);
                project_timeline[project_id] = j;
                break;
            }
        }
    }
    cout << ans;
    return 0;
}

思路

使用一个二维数组，来模拟每台机器的时间轴；这样一来，就知道某台机器在某个时间点的状态了

工序只能按序进行，所以使用一个数组project_timeline来记录每个工件的上一次耗时；下一次该工件的耗时应该接着上一次继续

那么就剩最后一个问题：如何插入某台机器的时间空挡？

令工件从其上一次的耗时开始，沿着机器的时间轴判断哪些连续的时间点是空闲的

若连续的空闲时间点满足工序的时间开支，则代表可以插入，可以回头将这一段空闲时间点设置为繁忙