题意理解

m个冰淇淋同时开始制作，每个都有各自的制作所需时间，只有在制作完成后才可以将其运走，并且汽车要返回。每次可以运不超过n个冰淇淋。要求总的运输时间最少，且运输次数也最少。注意，最后一次运输不计算回程的时间。

方法一

贪心
由于必须要等待冰淇淋制作完成才可以运输，所以先对制作时间进行排序，先制作先运输。

初始想法，每当有n个冰淇淋制作完成，我们进行一次运输。但是存在一个问题，如果等待倒数第二批中第n个冰淇淋耗费太长时间，会导致返回后剩下的冰淇淋（小于n个）已经做完很久了，这使得总的运输时间拉长。
举个例子：c=[10,20,30]，n=2，t=10。按照该思路，先送0、1号冰淇淋，再送2号，耗时50。实际可以先送0号，再送2、3号，耗时40。

换一个思路，因为每一批冰淇淋的发车时间是max(第n个完成时间，汽车返程的到达时间)，所以我们从后往前安排，每n个冰淇淋运输一次。这样可以保证最后一批冰淇淋都尽早发车，如图所示：

设每批的发车时间为time[i]。显然有

1. $time\left[1\right]>=time[1{]}^{\prime }time[1]>=time[1]\text{'}$time[1]>=time[1]′
2. $time\left[2\right]=max\left(time\right[1]+2t,cost[in\left]\right)time[2]=max(time[1]+2t,\; cost[in])$time[2]=max(time[1]+2t,cost[in])。cost[in]表示第i批中最后一个完成时间。
   $cost\left[in\right]>=cost[in{]}^{\prime }cost[in]>=cost[in]\text{'}$cost[in]>=cost[in]′——>$time\left[2\right]>=time[2{]}^{\prime }time[2]>=time[2]\text{'}$time[2]>=time[2]′
3. 依次类推，可能使最后一批发车时间提前，从而缩短总时间。

要使运输次数最少，那每次运输要尽可能装满n个。如果把n个冰淇淋分成两次运输，只可能导致后一部分的发车时间推迟，并不能缩短总时间。

具体代码如下：

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 cLen) {
        // write code here
        vector<int> cost,devide;
        int count=1,time=0;
        for (int i=0;i<cLen;i++)
            cost.push_back(c[i]);
        //完成时间从小到大排序
        sort(cost.begin(), cost.end());
        //计算哪些编号的冰淇淋是一起运输的，记录该批中第1个冰淇淋编号。
        for (int i=cLen-2;i>=0;i--)
        {
            if (count<n)
            {
                count++;
            }
            else
            {
                count = 1;
                devide.push_back(i+1);
            }
        }
        devide.push_back(0);
        //每一批冰淇淋的出发时间为该批第n个冰淇淋完成时间和汽车送上一批的返回达到时间的最大值。
        for (int i=devide.size()-2;i>=0;i--)
        {
            int goTime = max(time, cost[devide[i]-1]);
            time = goTime + 2*t;
        }
        time = max(time, cost[cLen-1]) + t;
        vector<int> ans;
        ans.push_back(time);
        ans.push_back(devide.size());
        return ans;
    }
};

时间复杂度：$O\left(MlogM\right)O(MlogM)$O(MlogM)。排序算法的时间复杂度。
空间复杂度：$O\left(M\right)O(M)$O(M)。开辟了新的数组用于排序和记录每批的运输情况。

方法二

动态规划
同样对制作完成时间进行排序。我们用dp[i]表示第i个冰淇淋被运输并返回所需的最短时间，那么假设已知第0~i-1个对应的最短时间。dp[i]可能和前面的n-1个冰淇淋的dp有关。第i个冰淇淋可能和其前面0~n-1个冰淇淋中的一部分一起运输。假设第j+1~i个冰淇淋一起运输，状态转移方程为：$dp\left[i\right]=max\left(c\right[i],dp[j\left]\right)+2tdp[i]=max(c[i],dp[j])+2t$dp[i]=max(c[i],dp[j])+2t。其中j可能的取值从i-n~i-1。使用divide数组记录运输时的分组情况。

动态规划的起始状态：
当i<n的时候，显然是等冰淇淋都制作完成一起运输时间最短。

注意，最后一次运输不需要返回。最短时间为dp[cLen-1]-t。

具体代码如下：

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 cLen) {
        // write code here
        sort(c,c+m);
        vector<int> dp(m,1000000);
        int count=0;//记录运输的次数
        //动态规划过程
        for (int i=0;i<cLen;i++)
        {
            //起始情况单独处理
            if (i<n)
            {
                dp[i] = min(dp[i],c[i]+2*t);
            }
            else
            {
                int index = -1,old = -1;
                for (int j=i-n;j<i;j++)
                {
                    if (dp[i]>max(dp[j],c[i])+2*t)
                    {
                        index = j;
                        dp[i] = max(dp[j],c[i])+2*t;
                    }
                }
                if (i%n==0) count++;
            }
        }
        count++;
        vector<int> ans;
        ans.push_back(dp[m-1]-t);
        ans.push_back(count);
        return ans;
    }
};

时间复杂度：$O(MlogM+MN)O(MlogM+MN)$O(MlogM+MN)。排序算法的时间复杂度，再加上动态规划的双重循环，对于每个冰淇淋i，遍历其前面n个冰淇淋来获得dp[i]。
空间复杂度：$O\left(M\right)O(M)$O(M)。开辟了新的数组dp。