洛谷P1065作业调度方案--Java解法

红太狼 2023-01-12 01:17 135阅读 0赞

# 洛谷P1065作业调度方案–Java解法 #

[题目链接][Link 1]

#### 废话 ####

此题目文字叙述比较多,首先要完全理解题目意思,开始没太理解题目意思浪费了很多时间，其实本题目就是一个简单模拟题目。另外，在对时间线以及各种数据的表示上面也需要花费一些时间考虑，本题目涉及变量众多，建议在命名的时候可以保证见名知意。

#### 思路 ####

首先，我们要**存储工件的安排顺序**，并能够知道**当前要安排的工件是安排工序几**以及**该工序应该在哪一个机器上面**。另外，我们应该知道**当前安排的工件的工序最早可以在什么时间开始**。此外，如何表示一个**机器的时间线**。因为没有想到更好的办法，因此我在表示时间线时用布尔类型的数组表示。

#### 上述数据结构 ####

**注意m表示机器数,n表示工件数**

>     记录当前工件要完成第几道工序
>       int[] workpiece=new int[n+1];

>     记录第i件工件在完成之前的工序后最早开始时间 初始化为0
>      int[] earlyTime=new int[n+1];

>     记录工序所需机器以及完成时间
>       static class Info{
>       	public int machineNum;
>       	public int time;
>       }
>       记录第i件工件第j道工序的机器号和加工时常
>       Info[][] info=new Info[n+1][m+1];

>     记录第i个机器的时间线 并初始化 false表示该时间点不忙 true表示在忙
>       注意每个机器时间线是理论上0-无穷大 但是计算机无法表示无穷数据,
>       且模拟数据量不会过大 因此我们时间线设置到0-10000即可
>       boolean[][] lineTime=new boolean[m+1][10001];

#### 时间细节处理 ####

从数据结构中我们知道,时间使用布尔类型的数据表示,那么思考一下。**如果一个工序可以从0时刻开始,加工时间为3小时,那么下标3我们应该设为false还是true?**  
在此必须说明一下，我们在查看0-3时刻是否可以插入时考虑的是0-1、1-2、2-3这三个时间段是否为闲。而下标0则代表的是0-1时刻，1代表1-2时刻，2代表2-3时刻，即我们在进行判断的时候仅仅判断下标0、1、2即可。而3则代表的是从3时刻开始到4时刻即3-4，**因此我们应该将下标3设置为false表示闲。**

#### 代码 ####

在数据结构表述清楚的情况下代码的书写如同水到渠成一样，没有什么难度。深深体会到了对数据的处理在程序中的重要性

import java.util.*;
    public class Main {
        
    	public static void main(String[] args) {
        
    		Scanner sc=new Scanner(System.in);
    		int m,n;
    		m=sc.nextInt();
    		n=sc.nextInt();
    		//记录当前工件要完成第几道工序 并进行初始化
    		int[] workpiece=new int[n+1];
    		for(int i=1;i<=n;i++) {
        
    			workpiece[i]=1;
    		}
    		//记录第i件工件在完成之前的工序后最早开始时间 初始化为0
    		int[] earlyTime=new int[n+1];
    		//记录安排顺序
    		int[] arrangeOrder=new int[m*n];
    		for(int i=0;i<m*n;i++) {
        
    			int pro=sc.nextInt();
    			arrangeOrder[i]=pro;
    		}
    		
    		//记录第i件工件第j道工序的机器号和加工时常
    		Info[][] info=new Info[n+1][m+1];
    		for(int i=1;i<=n;i++) {
        
    			for(int j=1;j<=m;j++) {
        
    				int machineNum=sc.nextInt();
    				info[i][j]=new Info();
    				info[i][j].machineNum=machineNum;
    			}
    		}
    		//记录完成时间
    		for(int i=1;i<=n;i++) {
        
    			for(int j=1;j<=m;j++) {
        
    				int time=sc.nextInt();
    				info[i][j].time=time;
    			}
    		}
    		//记录第i个机器的时间线 并初始化 false表示该时间点不忙 true表示在忙
    		 //注意每个机器时间线是理论上0-无穷大 但是计算机无法表示无穷数据,且模拟数据量不会过大 因此我们时间线设置到0-10000即可
    		boolean[][] lineTime=new boolean[m+1][10001];
    		for(int i=1;i<=m;i++) {
        
    			for(int j=0;j<=10000;j++) {
        
    				lineTime[i][j]=false;
    			}
    		}
    		//开始进行遍历 cur代表当前去除的工件号
    		for(Integer cur:arrangeOrder) {
        
    			int order=workpiece[cur];  			//order表示该工件要完成的工序
    			workpiece[cur]++;		
    			int eralytime=earlyTime[cur];  		//带工序的最早开始时间
    			Info curInfo=info[cur][order];  	//该工序的信息
    			for(int i=eralytime;i<=10000;i++) {
        
    				if(isArrange(i,curInfo,lineTime)) {
        
    					updateTime(i, curInfo, lineTime);
    					earlyTime[cur]=i+curInfo.time;
    					break;
    				}
    			}
    		}
    		//从最后时间中查找最大值
    		int res=-1;
    		for(int i=1;i<=n;i++) {
        
    			res=Math.max(res, earlyTime[i]);
    		}
    		System.out.print(res);
    		sc.close();
    		return;
    	}
    	//是否可以安排时间
    	static boolean isArrange(int startTime,Info inf,boolean[][] lineTime) {
        
    		int len=inf.time;
    		int num=inf.machineNum;
    		//对末尾时间的处理我们认为其完成在末尾时间左侧一点
    		for(int i=startTime;i<startTime+len;i++) {
        
    			if(lineTime[num][i]) return false;
    		}
    		return true;
    	}
    	
    	//更新时间线
    	static void updateTime(int startTime,Info inf,boolean[][] lineTime) {
        
    		int len=inf.time;
    		int num=inf.machineNum;
    		//对末尾时间的处理我们认为其可以作为下一个开始点因此设为忙
    		for(int i=startTime;i<startTime+len;i++) {
        
    			lineTime[num][i]=true;
    		}
    	}
    	//记录工序所需机器以及完成时间
    	static class Info{
        
    		public int machineNum;
    		public int time;
    	}
    }

[Link 1]: https://www.luogu.com.cn/problem/P1065