关注
本题需要最少的车辆,即尽可能组合出重量小于等于m的两人组。
首先,我们可以将所有人按体重升序,然后将最大体重和m比较,若最大体重大于等于m,则这个人只能一人占一辆车,车数量count++,然后将最大体重弹出,继续将剩下体重中最大的和m比较,逻辑同上,直到最大体重小于m时,停止弹出。
在剩余体重中,我们利用双指针,i指针指向最小体重,j指针指向最大体重,然后组合它们,即arr[i]+arr[j],和m比较,若小于等于m,则说明这两个人可以共享一辆车,车数量count++,然后i++,j--。如果arr[i]+arr[j]>m,则说明两个人无法共享一辆车,我们只能优先将这里车分配给较大体重的人,此时车数量count++,然后j--。
按上面逻辑移动双指针,最后可能会出现两种情况:
i > j 此情况下所有人均分配到了车,因此可以直接输出count作为题解
i === j 此情况下还有一个人未分配到车,因此需要count++,为这个人单独分配一辆车
查看原帖
3 评论
相关推荐
05-19 09:52
中国地质大学(武汉) Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 我的求职总结 #
12286次浏览 225人参与
# 辞职之后最想做的一件事 #
7985次浏览 87人参与
# 毕业季,给职场新人一些建议 #
11645次浏览 216人参与
# 选offer应该考虑哪些因素 #
9875次浏览 135人参与
# 我的实习日记 #
2417486次浏览 25273人参与
# 工作后会跟朋友渐行渐远吗 #
20514次浏览 159人参与
# 你小时候最想从事什么职业 #
90119次浏览 1690人参与
# 你想留在一线还是回老家? #
36344次浏览 439人参与
# 薪资爆料 #
102013次浏览 1039人参与
# 毕业后不工作的日子里我在做什么 #
167758次浏览 1484人参与
# 设计人如何选offer #
108025次浏览 707人参与
# 生物制药/化工校招攻略 #
42632次浏览 282人参与
# 比亚迪求职进展汇总 #
703376次浏览 3060人参与
# 第一份工作应该只看薪资吗 #
136869次浏览 1438人参与
# 你们公司哪个部门最累? #
14371次浏览 123人参与
# 你们的毕业论文什么进度了 #
1013956次浏览 9513人参与
# 秋招想进国企该如何准备 #
56673次浏览 363人参与
# 招聘要求与实际实习内容不符怎么办 #
98175次浏览 718人参与
# 工作中的卑微时刻 #
8770次浏览 54人参与
# 大学最后一个寒假,我想…… #
35463次浏览 454人参与