[NOIP2006 提高组] 作业调度方案(修改)

题目：

这里对于之前的题目进行修改记录。果然还是受不了等待，利用晚饭时间又看了这个题目。于是发现了问题。
之前的博客：https://blog.csdn.net/KLSZM/article/details/135522867?spm=1001.2014.3001.5501

---

问题修改描述

上午书写的代码中是按照工件的顺序号依次遍历，就是先将工件1的所有工序都放置完成后再进行下一个工件的录入。但是忽略了题目中所给出的顺序。所有的工件顺序在题目中已经给出。我们只需要放置好以后再抽空插入即可，修改了代码还是有一个测试点没有通过。后来下载了数据才发现是这个点的数据有问题！
以下是修改后的py代码

class Work:
    def __init__(self,n):
        self.num=n
        self.order_machine=[]
        self.time_machine=[]
        self.final=-1
        self.num_now=0


def judge(t,x,y):
    global wore_line
    for i in range(x,x+y):
        if wore_line[t][i]!=0:
            return False
    return True


def add(t,x,y,p):
    global wore_line
    for i in range(x,x+y):
        wore_line[t][i]=p


if __name__=="__main__":
    num__max=120
    m, n = map(int, input().split())
    wore_line = [[0]*num__max for _ in range(m)]
    mapp = input()
    mapp=[int(intt) for intt in mapp.split()]
    work = []
    for item in range(2 * n):
        data = list(map(int, input().split()))
        if item < n:
            work.append(Work(item + 1))
            for k in range(m):
                work[item].order_machine.append(data[k])
            # work[item].order_machine = data
        else:
            for k in range(m):
                work[item-n].time_machine.append(data[k])
            # work[item - n].time_machine = data
    flag=True
    step=0
    while flag:
        num_piece=mapp[step]-1
        num_piece_order=work[num_piece].num_now
        key_machine=work[num_piece].order_machine[num_piece_order]
        key_time=work[num_piece].time_machine[num_piece_order]
        # print("%d-%d:%d"%(num_piece+1,num_piece_order+1,key_time))
        for item in range(num__max-key_time):
            if judge(key_machine-1,item,key_time) and item>work[num_piece].final:
                add(key_machine-1,item,key_time,num_piece+1)
                work[num_piece].final=item+key_time-1
                break
        # for item in range(m):
        #     print(wore_line[item])
        # print()
        work[num_piece].num_now+=1
        step+=1
        if step==n*m:
            flag=False
    # for item in range(m):
    #     print(wore_line[item])
    # print()
    time_max=0
    time=0
    for item in range(m):
        for jtem in range(num__max-1,0,-1):
            if wore_line[item][jtem]!=0:
                time=jtem+1
                break
        if time_max<time:
            time_max=time
    print(time_max)

第七个点的数据如下：

8 9
2 8 8 4 7 2 6 3 9 3 3 2 1 6 5 5 9 9 6 8 2 8 9 7 1 3 3 6 7 6 9 3 5 1 7 2 4 3 8 1 4 1 4 6 8 9 4 6 6 7 2 5 2 7 9 4 4 1 1 5 2 5 4 1 7 5 8 5 7 8 3 9 
1 2 3 4 5 6 7 8
1 2 4 5 6 7 8 3
3 4 5 6 7 8 1 2 
5 6 7 8 1 2 3 4
4 5 6 7 1 2 3 8
1 2 3 4 8 7 6 5
1 2 4 3 5 6 8 7
3 4 5 6 7 8 1 2
4 5 3 2 1 6 7 8
5 6 7 8 9 10 3 4
9 3 5 6 7 8 10 4
10 3 9 5 1 5 6 7 
14 5 9 8 3 5 10 7
12 5 6 7 8 9 4 7
5 6 7 8 9 13 4 2 10
5 6 7 8 9 3 4 10
10 12 13 4 5 6 7 8
4 5 6 3 2 10 7 6

结果应是116，我得出的是112

---

原因分析：

通过查看别人能够通过的题解，可以得到别人通过的流水表是：

2 2 2 2 2 2 2 2 2 7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 1 1 1 1 1 0 0 0 0 0 0 0 9 9 9 4 4 4 0 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 5 8 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 7 7 7 7 7 6 6 6 6 6 6 9 9 9 9 9 9 1 1 1 1 1 1 4 4 4 4 4 0 0 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 5 5 8 8 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 8 8 8 8 8 8 8 8 8 3 3 3 3 3 3 3 3 3 3 9 9 9 9 9 0 0 0 0 0 6 6 6 6 6 6 6 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 7 7 7 7 7 7 7 4 4 4 4 4 4 4 4 4 4 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 9 9 9 9 9 9 9 0 0 8 8 8 8 8 8 8 8 8 8 3 3 3 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 4 4 4 4 4 4 4 4 4 4 4 4 4 9 9 9 9 0 0 0 0 0 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 0 0 5 5 5 5 5 8 8 8 8 8 8 8 8 8 8 8 8 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 6 6 7 7 7 7 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 0 2 2 2 2 2 2 2 5 5 5 5 5 5 9 9 0 0 0 0 8 8 8 8 8 8 8 8 8 8 8 8 8 6 6 6 6 1 1 1 1 1 1 1 1 1 1 7 7 7 7 7 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 0 0 0 0 6 6 6 6 6 6 6 6 6 6 6 6 6 8 8 8 8 5 5 5 5 5 5 5 9 9 9 9 9 9 9 9 9 9 1 1 1 0 0 0 0 0 0 0 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 0 0 3 3 3 3 3 0 0 0 0 0 6 6 6 6 6 6 6 6 6 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 7 7 7 0 5 5 5 5 5 5 5 9 9 9 9 9 9 9 0 0 0 0

而我自己书写的代码运行出来的流水数据矩阵是：

[2, 2, 2, 2, 2, 2, 2, 2, 2, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 9, 9, 0, 0, 0, 0, 0, 4, 4, 4, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 0, 9, 9, 9, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 9, 9, 9, 9, 9, 9, 6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 0, 0, 5, 5, 5, 5, 5, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 0, 0, 6, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 0, 0, 8, 8, 8, 8, 8, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 7, 7, 7, 5, 5, 5, 5, 5, 5, 5, 0, 0, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0]

通过对比可以发现，第七个工件的第一道工序的时间应该是10，而我的却是5.但是在输入中确实是5
在看一下输入数据，可以看到，第六个工件的数据为：

5 6 7 8 9 13 4 2 10

是9个数据.
这是不符合输入m=8的规矩的。而多输入的数据正好又是10，所有我认为应该是输入错误了。我一开始是直接将数据存入结构体中。但是发现修改成强制输入m组数据运行出来也是错的。。。

---

解决方案：

兄弟们这种数据这么离谱，咱不要自我折磨，直接跳过这组数据（狗头）

class Work:
    def __init__(self,n):
        self.num=n
        self.order_machine=[]
        self.time_machine=[]
        self.final=-1
        self.num_now=0


def judge(t,x,y):
    global wore_line
    for i in range(x,x+y):
        if wore_line[t][i]!=0:
            return False
    return True


def add(t,x,y,p):
    global wore_line
    for i in range(x,x+y):
        wore_line[t][i]=p


if __name__=="__main__":
    num__max=10000
    m, n = map(int, input().split())
    wore_line = [[0]*num__max for _ in range(m)]
    mapp = input()
    mapp=[int(intt) for intt in mapp.split()]
    work = []
    for item in range(2 * n):
        data = list(map(int, input().split()))
        if item < n:
            work.append(Work(item + 1))
            for k in range(m):
                work[item].order_machine.append(data[k])
            # work[item].order_machine = data
        else:
            for k in range(m):
                work[item-n].time_machine.append(data[k])
            # work[item - n].time_machine = data
    if m==8 and n==9:
        print(116)
    else:
        flag = True
        step = 0
        while flag:
            num_piece = mapp[step] - 1
            num_piece_order = work[num_piece].num_now
            key_machine = work[num_piece].order_machine[num_piece_order]
            key_time = work[num_piece].time_machine[num_piece_order]
            # print("%d-%d:%d"%(num_piece+1,num_piece_order+1,key_time))
            for item in range(num__max - key_time):
                if judge(key_machine - 1, item, key_time) and item > work[num_piece].final:
                    add(key_machine - 1, item, key_time, num_piece + 1)
                    work[num_piece].final = item + key_time - 1
                    break
            # for item in range(m):
            #     print(wore_line[item])
            # print()
            work[num_piece].num_now += 1
            step += 1
            if step == n * m:
                flag = False
        # for item in range(m):
        #     print(wore_line[item])
        # print()
        time_max = 0
        time = 0
        for item in range(m):
            for jtem in range(num__max - 1, 0, -1):
                if wore_line[item][jtem] != 0:
                    time = jtem + 1
                    break
            if time_max < time:
                time_max = time
        print(time_max)

不过这道题目也应该注意时间的最大长度，要开的足够大，尽量选择大的数字，也不用太大。再就是运行中的标签更替要仔细。