首页 > 试题广场 >

牛牛的冰激凌

[编程题]牛牛的冰激凌
  • 热度指数:162 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
公司让你负责m个冰激凌的运输。运输车的冷库只够装n个冰激凌,一次运输需要t分钟,返回也需要t分钟。每个冰激凌制作好有一个时间。求最短运输完所有冰激凌的时间,以及在时间最短的情况下最少运输次数。
示例1

输入

2,3,10,[10,30,40]

输出

[50,2]

备注:
(1≤n,m,t≤2000)

用例 1, 3, 10, [10, 10, 40]
答案 [70, 3] [60, 3]
都能通过验证,应该是系统用例不完备
详细代码如下:

    /**
     * 两个数表示答案
     * @param n int整型 一次运输的冰激凌数量
     * @param m int整型 总冰激凌数
     * @param t int整型 一次运输的时间
     * @param c int整型一维数组 表示每个冰激凌制作好时间<1e4
     * @return int整型一维数组
     */
    public int[] icecream (int n, int m, int t, int[] c) {
        // write code here
        
        quickSort(c, 0, m-1);
        
        int totalTime = t;
        int times = 1;
        int indicator = c[m-1];
        int[] gap = new int[m/n+1];
        int index = 0;
        for (int i = m-1-n; i >= 0; i-=n) {
            times++;
            int waitTime = indicator - c[i] - t*2;
            if (waitTime > 0) {
                totalTime +=  indicator - c[i];
                gap[index++] = waitTime;
            } else {
                totalTime += t*2;
                if (waitTime < 0) {
                    //这段逻辑去掉,牛客也能通过,应该是用例不完备造成的
                    waitTime = -waitTime;
                    totalTime -= waitTime;
                    while (waitTime>0 && index>=0) {
                        if (gap[index] > waitTime) {
                            gap[index] -= waitTime;
                            waitTime = 0;
                        } else {
                            waitTime -= gap[index];
                            gap[index--] = 0;
                        }
                    }
                    totalTime += waitTime;
                }
            }

            indicator = c[i];
        }

        totalTime += indicator;

        return new int[]{totalTime, times};
    }
    public static void quickSort(int[] list, int low, int high) {
        if (low < high){
            int middle =getMiddle(list, low, high);
            quickSort(list, low, middle - 1);
            quickSort(list,middle + 1, high);
        }
    }

    public static void swap(int[] param, int left, int right) {
        int temp = param[left];
        param[left] = param[right];
        param[right] = temp;
    }

    private static int getMiddle(int[] list, int low, int high) {
        int tmp =list[low];
        while (low < high){
            while (low < high && list[high] >= tmp) {
                high--;
            }
            list[low] =list[high];

            while (low < high&& list[low] <= tmp) {
                low++;
            }
            list[high] =list[low];
        }

        list[low] = tmp;

        return low;
    }

编辑于 2021-06-19 14:34:32 回复(0)