奇安信笔试题

题目描述：

　　一个车床能加工 10 种零件，用 0 到 9 代表着 10 种零件。现在用一个数组表示需要加工的零件，加工零件的顺序可以随意，每个零件都可以在 1 个单位时间加工完成，加工两个相同种类的零件之间需要 n 个单位时间（0 < n < 20）来准备材料，比如：加工完 8号零件后，直到 n 个单位时间后才能再次加工 8 号零件，此时车床可以去加工其它已经准备好材料的零件。请计算加工完所有零件的最短时间。

如，输入加工零件列表[1,1,1,2,3,3,3]，n = 2
最优加工顺序是：1, 2, 3, 1, 3, (等待)，1, 3
输出：8

思路：

这个题有点像操作系统中的系统调用问题，利用两个列表，一个保存材料的个数，一个保存材料的冷却时间。使用一个材料后，将这个材料的数量 -1，把这个材料的冷却时间设置为 n 秒；当材料的数量变为 0后，将这个材料删除，同时将这个材料的冷却时间也删除；当下一次挑选材料时，处于冷却时间中的材料不能加工，将其冷却时间 -1 秒；对于同时处于可用状态的材料（冷却时间 = 0），优先使用数量多的材料。所以，这就需要，每一轮材料加工后，都按照材料数量从大到小进行排序。当材料数量都处于 0 时，循环结束。

import java.util.*;

public class qiAnXin02 {
    public static void main(String[] args) {
        int[] tasks = {1,1,1,2,3,3,3};
        System.out.println(leastWorkTime(tasks,2));
    }
    public static int leastWorkTime (int[] tasks, int n) {
        int res = 0;
        Arrays.sort(tasks);
        List<Integer> nums = new ArrayList<>();
        List<Integer> times = new ArrayList<>();
        int count = 0;
        for(int i = 0; i < tasks.length; i++){
            if(i == 0){
                count++;continue;
            }
            if(tasks[i] == tasks[i-1]) count++; //重复个数
            else{
                nums.add(count); //统计每种材料个数
                times.add(0); //初始时间都为0，表示可以加工，没有处于冷却时间
                count = 1;
            }
        }
        nums.add(count); //最后一个种类的材料加入列表
        times.add(0); //最后一个材料的冷却时间为0
        BubbleSort(nums, times); //安装材料的个数 从大到小 排序
        while (nums.size() > 0){
            res += 1; //时间+1
            for(int i = 0; i < times.size(); i++){
                if(times.get(i) == 0){ //这个材料当前可以加工，将其材料个数减一
                    int tmp = nums.get(i) - 1;
                    if(tmp == 0){
                        nums.remove(i); //减一后，这个材料数量是否 = 0，等于 0 就将其删除
                        times.remove(i);
                        break;
                    }else { //否则，这个材料设置冷却时间 = n
                        nums.set(i, tmp);
                        times.set(i,n);
                    }
                }else { //这个材料当前处于冷却状态，将其冷却时间 -1
                    int tmp = times.get(i);
                    times.set(i, tmp-1);
                }
            }
            BubbleSort(nums, times); // 每一轮加工材料后，按照材料数量 从大到小 排序
        }
        return res;
    }
    public static void BubbleSort(List<Integer> nums, List<Integer> times){
        //材料、时间两个 List 联合冒泡排序，以材料数量为准，从大到小排序，和时间联合，每一种材料对应一个时间
        if(nums.size() == 0) return;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(nums.get(j) > nums.get(i)){
                    int tmp = nums.get(i);
                    nums.set(i, nums.get(j));
                    nums.set(j, tmp); //材料数量的大小下标交换
                    int tmpToTimes = times.get(i);
                    times.set(i, times.get(j));
                    times.set(j, tmpToTimes); //相应的，时间数组中，对应的下标也要一起交换
                }
            }
        }
    }
}

OJ 结果：提交 OJ，显示此题 AC 通过。