写题解
B题
发表于 2020-07-31 21:20:48
注意雪糕制作时间不是分开的,是一起制作的且一定要记得排序吐槽下传指针是啥玩意 官方讲解是dp即枚举当前一个雪糕,然后在一车可以送的雪糕数量去比对前面雪糕要不要一起送 零神是贪心,排序后从制作时间最大的进行贪心,给零神B站视频 才学疏浅,无代码了
avatar
256 浏览
(1)
(1)
题解 | #牛牛的冰激凌#
发表于 2021-07-23 19:38:03
题目描述
大意:公司让你负责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则代表它的前驱是在一开始原地等待然后一次性送出
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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</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]+2t);//做完[0,i]个冰激淋统一一趟送过去
}
int l=max(i-n,0);//最多可能由前n个状态转移过来
for(int j=l;j<i;j++){
int tmp=max(dp[j],c[i])+2t;//[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}
到这里大家应该都懂了,分解方法为
感性理解一下,在不白白浪费趟数的情况下,第一段越早去,最后一个蛋糕白白等待的可能性就少了很多。
算法思路
到这里,聪明的你肯定已经知道怎么写了,假如,第一段取,其余都取
对于,全部都取
趟数也就为
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> icecream(int n, int m, int t, int</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,为</int></int></int>