题目描述与示例
题目
一辆具有最大载重量的运送快递的货车正在运送若干重量不一的快递中，试计算出该货车最多能运载的快递数目。快递数量最多为1000个，货车的最大载重最为50000。
注：不考虑快递的体积。
输入
第一行输入每个快递的重量，用英文逗号隔开，如 5,10,2,11 第二行输入货车的最大载重量，如 20
输出
输出最多能装多少个快递，如 3
示例一
输入
5,10,2,11
20
输出
3
解题思路
为了能够尽可能地装下更多数量的快递同时不能让货车超载，我们贪心地从小重量的快递开始装载，并且累积当前快递的重量和cur_weight。直到cur_weight大于货车的最大运载量max_weight时，当前所运载的快递数目即为答案。
代码
Python
# 题目：2023Q1A-快递货车
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问
lst = list(map(int, input().split(",")))
lst.sort()
max_weight = int(input())
cur_weight = 0
ans = 0
for w in lst:
cur_weight += w
if cur_weight > max_weight:
break
ans += 1
print(ans)
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] input = scanner.nextLine().split(",");
int[] lst = new int[input.length];
for (int i = 0; i < input.length; i++) {
lst[i] = Integer.parseInt(input[i]);
}
Arrays.sort(lst);
int max_weight = scanner.nextInt();
int cur_weight = 0;
int ans = 0;
for (int w : lst) {
cur_weight += w;
if (cur_weight > max_weight) {
break;
}
ans++;
}
System.out.println(ans);
}
}
C++
“`C++
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string input;
getline(cin, input);
stringstream ss(input);
vector<int> lst;
int weight;
<pre><code>while (getline(ss, input, ',')) {
lst.push_back(stoi(input));
}
sort(lst.begin(), lst.end());
cin >> weight;
int cur_weight = 0;
int ans = 0;
for (int w : lst) {
cur_weight += w;
if (cur_weight > weight) {
break;
}
ans++;
}
cout << ans << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度：O(NlogN)。排序的时间复杂度。
空间复杂度：O(1)。忽略排序所使用的栈空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
