某印刷廠有 6項加工任務J1,J2,J3,J4,J5,J6,需要在兩臺機器Mi和M2上完
成。
在機器Mi上各任務所需時間為5,1,8,5,3,4單位;
在機器M2上各任務所需時間為7,2,2,4,7,4單位。
即時間矩陣為:
T1 = {5, 1, 8, 5, 3 ,4}
T2 = {7, 2, 2, 4, 7, 4}
請解決以下問題:
1.給出任務的最優加工順序,使得總加工時間最短;
2.計算加工完成所有任務的最短總時間;
算法流程:
1. 把ai<=bi 的放在數組list1,把ai>bi放在數組list2中
2. 把list1進行從小到大排序,list2從大到小排序
3. 把list1和list2進行合并,list1在前list2在后,這個順序即為加工的順序
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] A = new int[n];for (int i = 0; i < n; i++) {A[i] = sc.nextInt();}int[] B = new int[n];for (int i = 0; i < n; i++) {B[i] = sc.nextInt();}List<int[]> list1 = new ArrayList<>();List<int[]> list2 = new ArrayList<>();for (int i = 0; i < n; i++) {if (A[i] <= B[i]) {list1.add(new int[]{A[i], B[i]});} else {list2.add(new int[]{A[i], B[i]});}}list1.sort((o1, o2) -> o1[0] - o2[0]);list2.sort((o1, o2) -> o2[1] - o1[1]);List<int[]> list = new ArrayList<>();list.addAll(list1);list.addAll(list2);int AA = 0;int BB = 0;for(int[] arrs : list){AA+=arrs[0];BB = Math.max(AA,BB) + arrs[1];}System.out.println(Math.max(AA,BB));}
?list中即為最優的順序
最終輸出結果為最短時間