关注
可以使用贪心算法来解决这个问题。
首先,将所有车按照最大载客量从小到大排序。然后,从最小的车开始,将排队的人数尽可能地安排在这辆车上,直到这辆车无法再装下更多的人或者排队的人已经全部安排完毕。接着,再考虑下一辆车,重复上述过程,直到所有的车都被考虑过。
具体实现时,可以使用一个变量来记录已经安排的人数,以及一个变量来记录已经安排的车辆数。每次考虑一辆车时,从排队的人数中减去已经安排的人数,然后将剩余的人数尽可能地安排在这辆车上。如果这辆车已经被填满了,就将已经安排的车辆数加1,并将已经安排的人数清零,然后考虑下一辆车。
最后,返回已经安排的车辆数即可。
以下是Python代码实现:
```python
def max_cars(capacity, nums, k):
cars = sorted(zip(capacity, nums))
count = 0
total = 0
for c, n in cars:
total += n
if total <= c:
continue
count += 1
total = n
if total > 0:
count += 1
return count
```
时间复杂度为O(nlogn),其中n为车的数量。
查看原帖
点赞 1
相关推荐
牛客热帖
更多
正在热议
更多
# 你实习是赚钱了还是亏钱了? #
30818次浏览 242人参与
# CVTE求职进展汇总 #
23246次浏览 320人参与
# 京东开奖 #
472662次浏览 2681人参与
# 用一句话形容你的团队氛围 #
18729次浏览 179人参与
# 毕业论文进行时 #
6959次浏览 81人参与
# 你找工作是从容有余 or 匆忙滚爬? #
12319次浏览 95人参与
# 联影求职进展汇总 #
51593次浏览 325人参与
# 同bg的你秋招战况如何? #
174996次浏览 1022人参与
# 联影医疗求职进展汇总 #
6435次浏览 25人参与
# 海康威视工作体验 #
45841次浏览 157人参与
# 机械人与华为的爱恨情仇 #
137521次浏览 1013人参与
# 面对逼签的应对技巧 #
7465次浏览 38人参与
# 嵌入式岗知多少 #
58897次浏览 548人参与
# 找实习你看重大厂光环还是业务方向 #
41696次浏览 164人参与
# 中核求职进展汇总 #
28597次浏览 193人参与
# 我来点评面试官 #
16841次浏览 114人参与
# 扒一扒那些奇葩实习经历 #
126970次浏览 1100人参与
# 2022毕业即失业取暖地 #
116712次浏览 706人参与
# 哪些公司校招卡第一学历 #
220443次浏览 777人参与
# 校招薪资来揭秘 #
1878次浏览 17人参与
# 今年秋招是回暖还是遇冷 #
30942次浏览 195人参与