题解 | #牛牛的冰激凌#

思路

题目分析

题目输入的参数按顺序分别为：一趟车可以拉的冰激凌数量，冰激凌的总数量，一趟车运输（返回）的时间，每个冰激凌做好的时间
我们要如何安排运输方式，才能使得运输冰激凌的时间最短，并且求最短运输时间下的汽车运输的次数

我们发现如果想运输走最后一个冰激凌，他的时间是取决于两个因素的
- 一方面：它自身如果做好的时间很久很久，汽车已经把前面的都拉完了，就等着最后一个做好，最终获得最短时间和最终汽车趟数。
- 另一方面：汽车可以在它做好之前等着，这时一部分冰激凌已经装上车，等着最后一个做好再装车走。最终这个时间要权衡是否汽车有必要等后面的冰激凌。
- 因此重要的是我们发现后面的冰激凌最终的运输时间是取决于前面的情况的，因此有这种子结构的关系，推断使用动态规划。
另一种方法也可以引申为贪心，在方法二中介绍。

方法一：

我们以dp[i]作为运输车拉完第i个冰激凌后，返回到起点花费的最优时间
- 对于前n个冰激凌（一趟车可以拉走的量），只要等最后一个冰激凌做完就是最优的时间
- 对于n个后面的冰激凌，比如第i个(i>n)，我们对所有的j∈[i-n,i)范围的冰激凌运输情况dp[j]分别与c[i]比较，分析如果我们的运输车拉走包含第j个冰激凌的一车冰激凌并且回来后，所需的时间与比c[i]完成时间相比，取两者最大值，作为在第j个冰激凌处分车的总时间。
- 对于所有的j，我们选取一个最小的时间作为dp[i]的结果，因此其中选取的时间最小的对应的j，就是我们当前的最优解决方案，最终结果要减去一个返回的车程时间。

#
# 两个数表示答案
# @param n int整型 一次运输的冰激凌数量
# @param m int整型 总冰激凌数
# @param t int整型 一次运输的时间
# @param c int整型一维数组 表示每个冰激凌制作好时间<1e4
# @return int整型一维数组
#
class Solution:
    def icecream(self , n , m , t , c ):
        # write code here
        TIME_MAX = 0X7FFFFFFF
        c.sort()
        pre = [-1 for i in range(m)]
        dp = [TIME_MAX for i in range(m)]
        for i in range(m):
            if i < n:                                # 如果冰激凌数量在前n个数字，则根据最后的一个冰激凌做好时间，一趟拉完，
                dp[i] = c[i]+2*t
            else:                                    # 如果冰激凌数量超过n
                for j in range(i-n, i):              # 对第i个冰激凌，用已知的从i数前n个冰激凌的时间，做转移方程转移到第i根
                    cur = max(dp[j], c[i]) + 2*t     # 要做的比较就是前n个冰激凌中，运输包含第j根的车子开回来的时间，和第i根冰激凌做好的时间，选取较大的那个作为以[j+1,i]这些冰激凌为新一趟车的分割点
                    if dp[i] > cur:                  # 从中这些分割点筛选出最小时间的作为最优的装车解决方案
                        dp[i] = cur                  # 更新最优的时间
                        pre[i] = j                   # 跟踪最优的解决方案
        count = 0
        ice = m-1
        while(~ice):
            count += 1
            ice = pre[ice]
        return [dp[m-1]-t, count]

复杂度分析

时间复杂度： $O(mn)$ ，外层循环m项，内层循环n项
空间复杂度： $O(m)$ ，动态规划借助的额外空间为m级

方法二：贪心算法

假设我们有m可以整除n，我们可以理解每辆运输车满载发车就是最优的情况，只要多一辆车就是浪费时间和运输趟数
当m无法整除n的时候，一定是在上面的那个假设基础上多发一趟车即可，再多发就会浪费，因此多发的这一趟车一定是装载的余数数量（即m%n数量）的冰激凌，并且越早发越好，尤其是提前到首几个冰激凌，因为首先发走的这几个冰激凌运输的时间，后面的冰激凌也可以跟着做起来，最大程度的节省时间
因此贪心的方法可以让我们最快的获得最终结果

#
# 两个数表示答案
# @param n int整型 一次运输的冰激凌数量
# @param m int整型 总冰激凌数
# @param t int整型 一次运输的时间
# @param c int整型一维数组 表示每个冰激凌制作好时间<1e4
# @return int整型一维数组
#
class Solution:
    def icecream(self , n , m , t , c ):
        # write code here
        count = 0            # 运输次数
        carry = 0            # 运输的编号
        c.sort()             # 排序冰激凌产出时间
        if m%n == 0:         # 如果能整除则每趟运满就是最优的方案
            count = m/n
            carry = n-1
        else:                # 如果不能整除则需要先发车不能整除的余出来的数量，这个数量的冰激凌作为首发运输
            count = m//n+1
            carry = m%n - 1
        time = 0
        while(carry < m):
            time = max(time, c[carry]) + 2*t
            carry += n
        time -= t                                 # 减去最后一个返回时间
        return [time, count]

复杂度分析

时间复杂度： $O(mlogm)$ ，排序数组的时间消耗
空间复杂度： $O(1)$ ，没有额外的申请