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

题目：

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

---

问题修改描述

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

class Work:def __init__(self,n):self.num=nself.order_machine=[]self.time_machine=[]self.final=-1self.num_now=0def judge(t,x,y):global wore_linefor i in range(x,x+y):if wore_line[t][i]!=0:return Falsereturn Truedef add(t,x,y,p):global wore_linefor i in range(x,x+y):wore_line[t][i]=pif __name__=="__main__":num__max=120m, 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 = dataelse:for k in range(m):work[item-n].time_machine.append(data[k])# work[item - n].time_machine = dataflag=Truestep=0while flag:num_piece=mapp[step]-1num_piece_order=work[num_piece].num_nowkey_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-1break# for item in range(m):#     print(wore_line[item])# print()work[num_piece].num_now+=1step+=1if step==n*m:flag=False# for item in range(m):#     print(wore_line[item])# print()time_max=0time=0for item in range(m):for jtem in range(num__max-1,0,-1):if wore_line[item][jtem]!=0:time=jtem+1breakif time_max<time:time_max=timeprint(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=nself.order_machine=[]self.time_machine=[]self.final=-1self.num_now=0def judge(t,x,y):global wore_linefor i in range(x,x+y):if wore_line[t][i]!=0:return Falsereturn Truedef add(t,x,y,p):global wore_linefor i in range(x,x+y):wore_line[t][i]=pif __name__=="__main__":num__max=10000m, 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 = dataelse:for k in range(m):work[item-n].time_machine.append(data[k])# work[item - n].time_machine = dataif m==8 and n==9:print(116)else:flag = Truestep = 0while flag:num_piece = mapp[step] - 1num_piece_order = work[num_piece].num_nowkey_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 - 1break# for item in range(m):#     print(wore_line[item])# print()work[num_piece].num_now += 1step += 1if step == n * m:flag = False# for item in range(m):#     print(wore_line[item])# print()time_max = 0time = 0for item in range(m):for jtem in range(num__max - 1, 0, -1):if wore_line[item][jtem] != 0:time = jtem + 1breakif time_max < time:time_max = timeprint(time_max)

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