题解 | #牛牛的冰激凌#

牛牛的冰激凌

http://www.nowcoder.com/practice/0fa7af397f7746daacb07169fa8df5d5

题意理解

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

方法一

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

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

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

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

  1. time[1]>=time[1]time[1]>=time[1]' time[1]>=time[1]
  2. time[2]=max(time[1]+2t,cost[in])time[2]=max(time[1]+2t, cost[in])time[2]=max(time[1]+2t,cost[in])。cost[in]表示第i批中最后一个完成时间。
    cost[in]>=cost[in]cost[in]>=cost[in]'cost[in]>=cost[in]——>time[2]>=time[2]time[2]>=time[2]'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(MlogM)O(MlogM)O(MlogM)。排序算法的时间复杂度。
空间复杂度:O(M)O(M)O(M)。开辟了新的数组用于排序和记录每批的运输情况。

方法二

动态规划
同样对制作完成时间进行排序。我们用dp[i]表示第i个冰淇淋被运输并返回所需的最短时间,那么假设已知第0~i-1个对应的最短时间。dp[i]可能和前面的n-1个冰淇淋的dp有关。第i个冰淇淋可能和其前面0~n-1个冰淇淋中的一部分一起运输。假设第j+1~i个冰淇淋一起运输,状态转移方程为:dp[i]=max(c[i],dp[j])+2tdp[i]=max(c[i],dp[j])+2tdp[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(M)O(M)O(M)。开辟了新的数组dp。

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 10:18
点赞 评论 收藏
分享
10-13 17:47
门头沟学院 Java
wulala.god:图一那个善我面过,老板网上找的题库面的
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务