题解 P1065 【作业调度方案】

· · 题解

题目解析

这是一道模拟题，主要需要考虑以下几个约束条件：

  1. 每个工件的下一个工序必须在上一个工序之后
  2. 同一台机器同一时刻只能加工一个工件
  3. 按题目顺序安排下一个工件

按照题目说的做，不会错。

我的题解一般会放一组福利数据，这次也不例外。洛谷官方数据测试点#2奉上，附解释。

数据

input

3 3
1 1 1 2 3 3 2 2 3
1 2 3
2 1 3
2 3 1
7 2 4
3 2 5
3 2 3

output

18

explain(可怜我画图花了好久)

附：我的代码

#include <stdio.h>

int m, n;
int list[501];
struct Information {
    int id;
    // 在第 id 台机器上加工
    int cost;
    // 花费 cost 时间
} a[21][21];
// a[第几个工件][第几步]
int mac[21][100001] = {0};
// mac[机器编号][时间（话说我也不知道时间最大是多少，反正在空间限制内尽量大）]
int step[21] = {0};
// 每个工件加工到了第几步
int las_time[21] = {0};
// 每个工件上次是 las_time[工件编号] 时加工完的
int ans = 0;

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m * n; i++) {
        scanf("%d", list + i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j].id);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j].cost);
        }
    }
    // 以上：读入
    for (int i = 1; i <= m * n; i++) {
        int now = list[i];
        step[now]++;
        int id = a[now][step[now]].id, cost = a[now][step[now]].cost;
        /* 调试代码 */ // printf("%d: now = %d, id = %d, cost = %d\n", i, now, id, cost);
        int s = 0;
        for (int j = las_time[now] + 1; ; j++) {
            if (mac[id][j] == 0) {
                s++;
            } else {
                s = 0;
            }
            if (s == cost) {
                for (int k = j - cost + 1; k <= j; k++) {
                    mac[id][k] = 1;
                }
                /* 调试代码 */ // printf("(%d~%d. \n", j - cost + 1, j);
                if (j > ans) ans = j;
                las_time[now] = j;
                break;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

(无耻地求踩，太烂了)