题目描述

大意：公司让你负责m个冰激凌的运输。运输车的冷库只够装n个冰激凌，一次运输需要t分钟，返回也需要t分钟。每个冰激凌制作好有一个时间。求最短运输完所有冰激凌的时间，以及在时间最短的情况下最少运输次数。
（这题真的不知道怎么写个暴力了，如果写个暴力，不失正确性，发现不就是记忆化搜索？？？递推的顺序也不难发现，跟dp大同小意，所以此题我写暴力方法了）

算法一：动态规划

思路引入

• （此处默认已经将c数组排序过了）
• 一个很直观的思路，如果我当前有n个冰淇淋，并且我人已经在工厂了，我肯定是立马送出
• 因为如果我在原地还等待，就算制作出了n+1个冰淇淋，我也依旧不能运输出去
• 因为冰淇淋没有差别，如果第i个冰淇淋和第i+1个都生产出来了，所以我们没必要选择第i+1个冰淇淋运出去,而不运第i个
• 所以，基于这种思想，我们可以这样定义dp的状态

  dp[i]代表运输完第i个冰淇淋并且回到工厂所需要的最短时间

• 注意此处还需要回到工厂，也就代表第m-1个也回去了，实际上他不需要回去，那么我们最后要的答案其实是

  状态转移

• 因为我们一次可以运送的冰淇淋的数量为，
• 所以那么对于，我们已经知道了i的前面n-1个冰淇淋的状态。

• 即的时间基础上面，在送出这个区间所有的冰淇淋
  
  • 这边的可能有同学没看懂，因为要保证包括第i个冰淇淋的情况，前面还有个冰淇淋，并且已经送完了第j个冰淇淋的情况，也就是说至少得有个冰淇淋，但是下标是从0开始的，所以我们此处为
• (注意：上面对于的是的情况，所以我们还需要考虑的情况)
• 显然我们还需要考虑的一种情况，就是一开始什么都不送，等到第个冰淇淋做好然后送出去，其中
  
• 然后得到了j到i的转移方程 ，（取max是因为下标要合法）
• 接下来我们还要求总的趟数，我们只需要在dp的时候记录该状态是由哪一个转移过来的，倒序追踪的时候计数
• 借用pre[]数组来记录前驱，初始化为-1，如果为-1则代表它的前驱是在一开始原地等待然后一次性送出

代码实现

#define pb push_back
#define inf 0x3f3f3f3f
class Solution {
public:
    /**
     * 两个数表示答案
     * @param n int整型 一次运输的冰激凌数量
     * @param m int整型 总冰激凌数
     * @param t int整型 一次运输的时间
     * @param c int整型一维数组 表示每个冰激凌制作好时间<1e4
     * @param cLen int c数组长度
     * @return int整型vector
     */
    vector<int> icecream(int n, int m, int t, int* c, int len) {
        vector<int> ans;//记录答案 
        vector<int> dp(m,inf);//dp[i]代表运输完第i个物品并且回到工厂所需要的最短时间
        //所以我们求解的也就是dp[m-1]-t,就是最后一趟不需要回到工厂 
        vector<int> pre(m,-1);//记录前驱 
        sort(c,c+m);//排序c数组 
        for(int i=0;i<len;i++){
            if(i<n){//因为[0,n-1]的冰激淋可能没有前驱 
                dp[i]=min(dp[i],c[i]+2*t);//做完[0,i]个冰激淋统一一趟送过去 
            }
            int l=max(i-n,0);//最多可能由前n个状态转移过来 
            for(int j=l;j<i;j++){
                int tmp=max(dp[j],c[i])+2*t;//[j+1,i]之间的冰激淋全部都由这一趟运送过去 
                //第j个冰激淋运输 
                if(dp[i]>tmp){//假如比当前的dp[i]更优，则更新答案 
                    dp[i]=tmp;
                    pre[i]=j;//记录前驱
                    //此处前驱用于计算运输次数 
                    //也可以用于追踪最优方案， 
                }
            }
        }
        int cnt=0,now=m-1;//cnt用于记录最少运输次数
        //now代表当前是在第几个冰激凌制作好后去运输的 
        while(~now){//当前now合法,即now不等于-1,因为-1的反码是0所以可以这样写 
            cnt++;//去的趟数加一 
            now=pre[now];//追踪前驱 
        }
        ans.pb(dp[len-1]-t);//最后一趟不需要返回到工厂 
        ans.pb(cnt);// 
        return ans;
    }
};

复杂度分析

• 时间复杂度，排序为，动态规划两层循环为,理论上应该是,但是数据中比的阶大，所以总的时间复杂度为
• 空间复杂度，定义了动态数组ans,dp,pre，为

  算法二：贪心

  引入

• 其实这题真的很难看出来是贪心，因为确实很难证明贪心（网上能找到的博客我瞅了一眼，发现没人证明……）
• 不过我这边尽量不用抽象的纯数学来证明，我尽量讲的通俗易懂一点
• 以下有好几个需要证明的，我尽量递进得来讲

  证明：运送数量贪心，m<=n

• 上面的动态规划中，我已经讲过了，能如果当前有n个冰淇淋可以运出去，那么等下一个冰淇淋制作出来是毫无意义的
• 现在我们需要思考的问题，如果需要运送的数量，那么我们是否有可能花费两趟去比花费一趟去来的优？
• 答案是不可能的。为什么？
• 如果花费一趟去，我们最后花费的时间是，而花费两趟的时间是
• 显然有
• 就是说，花费一趟去的代价不劣于花两趟去的代价，想必聪明的你肯定知道这种情况选哪种情况去。

  证明：贪心，n<m<=2n

• 当m的个数在之间的时候，我们是否有可能花费三次去运输？
• 答案是不可能的。为什么？
• 因为，如果其中连续的两趟拼接起来小于n，根据上述结论，我们则会花费一趟运输
• 如果大于n，则设两趟的长度为和，显然二者都不能超过n
• 故有，答案为
• 因为我们以及排序过一遍了，显然c[m-n]是最小的，那么有：**不会劣于其他答案**

  证明：贪心，对于任意m

• 尽过上面的两个证明，相信大家已经有点感觉了
• 对于贪心法的证明，我们往往采用替换法，即该决策替换掉最优解，不会劣与最优解，即该决策是最优解，上面的max那句话我已经用到了
• 想必这里大家也应该知道了怎么做了，对的，数学归纳法
• 如果还不懂的话，我举个简单的例子，假设对于，我们取走第一段，剩下的不就是转换为的情况吗？
• 如果取走最后一段，也是的情况，为了满足第二个证明的结论，故唯一的分解方法为{m-2n,n,n}
• 到这里大家应该都懂了，分解方法为
• 感性理解一下，在不白白浪费趟数的情况下，第一段越早去，最后一个蛋糕白白等待的可能性就少了很多。

  算法思路

• 到这里，聪明的你肯定已经知道怎么写了，假如,第一段取，其余都取
• 对于，全部都取
• 趟数也就为

  代码实现

  class Solution {
  public:
    vector<int> icecream(int n, int m, int t, int* c, int len) {
        sort(c,c+m);//排序c数组 
        int cnt,ans=0,sta;//趟数，最小时间值，第一趟从第几个冰淇淋开始运送
        if(m%n)cnt=m/n+1,sta=m%n-1;//不能整除得多运送一趟
        else cnt=m/n,sta=n-1;//下标0开始，所以是第n个物品实际为c[n-1]
        for(int i=sta;i<m;i+=n){
            ans=max(ans,c[i])+2*t;//上一次返回来的时间，和这个冰淇淋做好的时间，取最大值，来回需要加上2t
        }
        ans-=t;//最后一趟不需要回工厂
        return {ans,cnt};
    }
  };

  复杂度分析

• 时间复杂度，排序，n最小值为1，所以贪心遍历一遍的最坏情况为，总得为
• 空间复杂度，定义了数字ans,cnt，sta，为