2023-09-02 18:04 门头沟学院 嵌入式工程师
关注
关于小米笔试
第二个算法题，有n个应用，每个应用有耗电量和最小要求电量，求最小持电量导致可以满足所有应用耗电量之和，若最小持电量大于电池容量则输出-1。求大佬指点迷津！
全部评论
牛客365128435号
The University of New South Wales 后端工程师
只过了66
Rookie_fly
门头沟学院 .NET
一次遍历，算出 所有最小要求电量－耗电量的最小值a，算出所有耗电量之和b，最高要求电量c，取a+b和c中最大的那个，就是答案，如果答案大于4800，就输出-1，这是我a的做法
拒绝内耗_黑化版
华为_软件开发工程师
我是用a[1]降序-a[0]升序做的，考虑了4800，但是还是只过了83，不知道为啥
要暴富的牛肉丸很细致
沈阳航空航天大学 Java
动态规划做的，dp是第n个应用最小持电量，但是只过了50%
牛客491255974号
门头沟学院 自动化
或者，使用电量求和得到a，然后和剩余电量最大值进行比较，得到他俩的最大值b。然后b+1，就是最后的输出值。如果a＞4800的话，输出值为-1
小马哥写程序
蚌埠坦克学院 后端工程师
我是贪心，把除了消耗最大的一个任务外的任务消耗电量累加得到sum，然后从消耗最大任务中取初始电量最小的电量得到min，然后sum+min 返回，并排除大于4800的电量，最后通过率83%
__OWo__
佛光大学 C++
相同耗电量下，优先跑要求电量高的；
相同要求电量下，优先跑耗电量低的；
不同耗电、不同要求电量下（如下👇），无法简单比较决定排序（排序做的不能AC的原因）；
15：17、14：15 结果30 29-32
1：15、5：16 结果17 6-31
【为了解决这种情况】
进行简单推理：两个(a:b)，(c:d)，此时a!=c ;b!=d;
设电量为n (n>= max(b,d));
① 当n-a>=d 时，可以通过
所以 n_min = max(a+d, b);
当我们交换顺序 n_min = max(c+b,d);
所以为了让n最小化，我们排序的逻辑此时为：
max(a+d, b) < max(c+b, d) ? 【这么排(a,b)→(c,d)】 :【否则这样排(c,d)→(a,b)】；
【收尾】
排序策略写好了，我们在定义一个自定义排序函数即可，调用sort；
从头到尾贪婪计算电量即可；
biubiubiu666
门头沟学院 嵌入式软件开发
0.17，直接输出-1就有😂😂😂
刚炸的土豆
门头沟学院 Java
我是排序，先按最小电量升序排，再按耗电量降序排，之后贪心。结果过了50%，没考虑超出容量的-1情况。
Offer四面八方来求求了
门头沟学院 测试开发
卧槽，前面的是耗电量啊，我以为是序号呢
牛客501161481号
电子科技大学 集成电路IC设计
用总耗电量之和加上单个任务执行后的最小电量，判断是否超过最大电量就OC了。感觉有问题，但是过了
等待我的狗屎运
门头沟学院 C++
下限的上限是最大要求电量，上限是最大要求点量+所有耗电量的和。然后循环判断
mmncw
青岛上清路小学 算法工程师
贪就完事了
相关推荐
不愿透露姓名的神秘牛友
08-30 11:51
点赞 评论 收藏
分享
查看15道真题和解析 08-30 23:18
University of Oxford 测试开发 
投递小米集团等公司10个岗位 点赞 评论 收藏
分享
