题意

有 个冰淇淋需要运输，每个冰淇淋有一个完成时间。货车一次能运 个，来回均要 分钟，求运走所有冰淇淋的时间。

解法1：DP

将冰淇淋按完成时间排序，显然最优方案每次运送的一定是时间相邻的一段冰淇淋。

记 dp[i] 为运送完第 个冰淇淋再返回的最早时间。可以得到递推式 ，另外用数组 计算运输次数。
可以递推求解，最终答案是

代码

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), cnt(m);

        for(int i=0; i<m; ++i){
            if(i<n){
                dp[i]=c[i]+t*2;// 第一次运输
                cnt[i]=1;
            }
            else{
                dp[i]=1e9;
                for(int j=1; j<=n; ++j){
                    int now=max(dp[i-j],c[i])+t*2; // 递推
                    if(now<dp[i] || now==dp[i] && cnt[i-j]+1<cnt[i]){
                        dp[i]=now;
                        cnt[i]=cnt[i-j]+1;
                    }

                }
            }
        }
        vector<int> ret;
        ret.push_back(dp[m-1]-t);
        ret.push_back(cnt[m-1]);
        return ret;
    }
};

复杂度分析

空间复杂度：需要维护DP和cnt数组，
时间复杂度：排序+DP，

解法 1': 单调栈优化DP

注意到该递推关系满足滑动窗口模型，可以利用单调栈来维护最优取值点，将递推复杂度优化到 。
比如窗口大小为 3，取值序列为 1,9,2,6,0,8,1,7 ，则维护顺序如下：

代码

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), cnt(m);
        deque<int> sta(1,-1);
        for(int i=0; i<m; ++i){
            while(!sta.empty() && sta.front()+n<i) sta.pop_front(); // 最优值点已过期
            if(sta.front()==-1){ // 第一次运输
                dp[i]=c[i]+t*2;
                cnt[i]=1;
            }
            else{
                dp[i]=max(dp[sta.front()], c[i])+t*2; // 最优值点
                cnt[i]=cnt[sta.front()]+1;
            }
            while(!sta.empty() && dp[sta.back()]>dp[i]) sta.pop_back(); // 维护单调性
            sta.push_back(i);
        }
        vector<int> ret;
        ret.push_back(dp[m-1]-t);
        ret.push_back(cnt[m-1]);
        return ret;
    }
};

复杂度分析

空间复杂度：维护数组
时间复杂度：排序 ，DP ，共

解法2：贪心

如果 是 的倍数，那么最优策略显然每做好 个，（且车回来了）就运一次。
而如果 不是 的倍数，由于（对车而言）晚运不如早运，因此第一次运 个，后面依然是每满 个就运一次。

具体实现时，把冰淇淋按完成时间排序，然后对每个模 与 同余位置的冰淇淋，以它作为最后一次停车时间计算一下答案，最后取 max 即可。

代码

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);
        int tm_ = 0, cnt = 0;
        for(int i = m-1; i >= 0; i -= n){
            cnt++;
            tm_ = max(tm_, c[i]+t*(cnt*2-1)); // 运输
        }
        vector<int> ret;
        ret.push_back(tm_);
        ret.push_back(cnt);
        return ret;
    }
};

复杂度分析

空间复杂度
时间复杂度：排序 ，求解 ，共