题解 | #牛牛的冰激凌#
牛牛的冰激凌
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个冰淇淋运输一次。这样可以保证最后一批冰淇淋都尽早发车,如图所示:
设每批的发车时间为time[i]。显然有
- time[1]>=time[1]′
- time[2]=max(time[1]+2t,cost[in])。cost[in]表示第i批中最后一个完成时间。
cost[in]>=cost[in]′——>time[2]>=time[2]′ - 依次类推,可能使最后一批发车时间提前,从而缩短总时间。
要使运输次数最少,那每次运输要尽可能装满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(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])+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)。排序算法的时间复杂度,再加上动态规划的双重循环,对于每个冰淇淋i,遍历其前面n个冰淇淋来获得dp[i]。
空间复杂度:O(M)。开辟了新的数组dp。