C++: 最大装载快递数量 - 贪心算法解题

{"title":"C++: 题目描述\n有一批快递要装上一辆载重量为 c 的快递车进行运送。第 i个快递的重量为 Wi。由于每件快递都很小，几乎不占快递车的空间，但是都比较重。为了节省成本，因此需要考虑在装载体积不受限制的情况下，将尽可能多的快递装上快递车，请你编程帮助快递小哥求出来最多能装载多少件快递。\n\n输入描述\n第一行共两个整数N，c，表示快递的件数和快递车的载重量。\n\n第二行共有 N 个整数，分别表示快递的重量Wi。\n\n输出描述\n共一行，输出 1个整数，表示最多能装载的快递件数。\n\n样例1\n输入\n8 400\n100 200 50 90 150 50 20 80\n输出\n6\n提示\n对于 100% 的数据，N≤100，c≤10000。","content":"解题思路：\n1. 首先将快递的重量按照非递增的顺序排序。\n2. 从重量最大的快递开始，依次将快递装入快递车，直到快递车的载重量达到上限。\n3. 统计装载的快递件数。\n\n具体实现步骤：\n1. 读取输入的N和c。\n2. 创建一个大小为N的数组weights，用来存储快递的重量。\n3. 使用for循环读取N个快递的重量并存储到weights数组中。\n4. 将weights数组按照非递增的顺序排序。\n5. 创建一个变量count，用来记录已经装载的快递件数。\n6. 创建一个变量sum，用来记录已经装载的快递的重量之和。\n7. 使用for循环遍历weights数组，如果sum加上当前快递的重量小于等于c，则将当前快递装入快递车，同时更新sum和count。\n8. 输出count，表示最多能装载的快递件数。\n\n时间复杂度分析：\n1. 排序的时间复杂度为O(NlogN)。\n2. 遍历weights数组的时间复杂度为O(N)。\n3. 总的时间复杂度为O(NlogN)。\n\n空间复杂度分析：\n1. 使用了一个大小为N的数组weights，空间复杂度为O(N)。"}