题解 | #牛牛的冰激凌#

题意整理

总共有m个冰淇淋要运输，运输车一次最多装n个，来回一趟各需t分钟。
现在每个冰淇淋都有一个制作时间，求怎样运输花费时间最短，最短时间下怎样运输次数最少。

方法一（动态规划）

1.解题思路

状态定义: $dp[i]$ 表示运输完第i个物品并且回到工厂所需要的最短时间。
状态初始化:将所有状态置为Integer型整数最大值。
状态转移：如果第i个冰淇淋之前有生产冰淇淋，则最多从第 $i-n$ 个冰淇淋算起，找到运完这一组冰淇淋（最多n个一组）所需的时间，如果时间小于当前的状态，则进行跟新，同时记录前驱状态。
运完最后一个冰淇淋的时间即是最短花费时间，运输次数可根据前驱数组倒推出来。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 两个数表示答案
     * @param n int整型 一次运输的冰激凌数量
     * @param m int整型 总冰激凌数
     * @param t int整型 一次运输的时间
     * @param c int整型一维数组 表示每个冰激凌制作好时间<1e4
     * @return int整型一维数组
     */
    //Integer型整数最大值
    int INF=Integer.MAX_VALUE;
    public int[] icecream (int n, int m, int t, int[] c) {
        //记录转移前的状态
        int[] pre=new int[m];
        //dp[i]表示运输完第i个物品并且回到工厂所需要的最短时间
        int[] dp=new int[m];
        //初始化
        Arrays.fill(pre,INF);
        Arrays.fill(dp,INF);
        //排序
        Arrays.sort(c);
        for(int i=0;i<m;i++){
            //如果小于n，直接赋值
            if(i<n){
                dp[i]=c[i]+2*t;
            }
            //如果小于n，从0开始算，否则从i-n处开始
            int start=Math.max(0,i-n);
            for(int j=start;j<i;j++){
                //计算j+1到i区间的冰淇淋装车运输需要多长时间
                int tmp=Math.max(dp[j],c[i])+2*t;
                //跟新dp[i]
                if(dp[i]>tmp){
                    dp[i]=tmp;
                    pre[i]=j;
                }
            }
        }
        //最少运输次数
        int cnt=0;
        int cur=m-1;
        //从终点处m-1往前推，直到没有前驱
        while(cur!=INF){
            cnt++;
            cur=pre[cur];
        }
        return new int[]{dp[m-1]-t,cnt};
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度是 $O(mlog_2m)$ ，主循环体最多执行 $m*n$ 次，所以最终的时间复杂度为 $O(mlog_2m+m*n)$ 。
空间复杂度：需要额外大小为m的dp数组和pre数组，所以空间复杂度为 $O(m)$ 。

方法二（贪心）

1.解题思路

为了运输时间最短，肯定先制作完的，先运走，所以先对数组排序，然后每次尽可能多地往运输车里装，所以每满 $n$ 个运输一次。当有一组不足 $n$ 个时，考虑将其放在前面装车运走，因为运输消耗的时间，刚好可以抵消其它冰淇淋制作的时间。

首先对 $c$ 数组排序。
然后将所有冰淇淋 $n$ 个一组装车运走，如果有一组不足 $n$ 个，从第 $m%n-1$ 个开始，对应次数为 $m/n+1$ 。如果每组都是 $n$ 个，则从第 $n-1$ 个开始，对应次数为 $m/n$
注意最后一趟运完不需要返回，所以最后的时间要减去 $t$ 。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 两个数表示答案
     * @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) {
        //排序
        Arrays.sort(c);
        //初始化最短时间，最少次数，从第几个冰淇淋开始运输
        int res=0;
        int cnt=0;
        int start=0;
        //如果余数为0，从第n-1个开始，次数为m/n
        if(m%n==0){
            start=n-1;
            cnt=m/n;
        }
        //如果余数不为0，从第m%n-1个开始，次数为m/n+1
        else{
            start=m%n-1;
            cnt=m/n+1;
        }

        //每隔n个运输一次
        for(int i=start;i<m;i+=n){
            res=Math.max(res,c[i])+2*t;
        }
        //最后一趟不需返回
        res-=t;
        return new int[]{res,cnt};
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度是 $O(mlog_2m)$ ，主循环体最多执行 $m/n+1$ 次，所以最终的时间复杂度为 $O(mlog_2m)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。