华为 · 贪心 · 算法编程题
华为 贪心 N ≤ 1e3 时限 3 秒 / 256 MB

题目描述

在一个自动化的大型仓储中心，机器人需要将一批货物打包到不同的集装箱中。
每个集装箱都有其固定的最大载重量，同时每件货物也有其自身的重量。
为了高效利用空间，一个集装箱内可以装入多件货物，但前提是货物的总重量不能超过集装箱的最大载重。
然而，由于货物是不可分割的，一件货物必须被完整地装入某一个集装箱中，不能分开装。
作为调度系统的工程师，您的任务是编写一个算法，以确定最多可以成功装箱多少件货物。
给定一个代表集装箱载重的数组 C 和一个代表货物重量的数组 W 。请找出一个最优的装箱方案，使得能够被装箱的货物数量最多。

输入输出

输入描述
输入共四行：
1. 第一行为一个整数 N ，表示集装箱的数量。
2. 第二行为一个包含 N 个整数的数组 C = c_1, c_2, ..., c_N ，代表每个集装箱的最大载重量，用空格分隔。
3. 第三行为一个整数 M ，表示货物的总数。
4. 第四行为一个包含 M 个整数的数组 W = w_1, w_2, ..., w_M ，代表每件货物的重量，用空格分隔。
1 ≤ N ≤ 1000
1 ≤ M ≤ 1000
1 ≤ c_i ≤ 10000
1 ≤ w_j ≤ 10000
输出描述
输出一个整数，表示最多可以成功装箱的货物数量。
如果没有任何一件货物可以被装箱，则输出 0 。

样例共 1 组

样例 1
输入
8
50 50 1 14 32 15 2 22
11
88 42 14 25 14 9 40 35 50 17 32
输出
6

算法解析依据充分

考点：贪心

数据规模 N ≤ 1e3 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 1e3，M ≤ 1e3
  • 元素值域：c_i ≤ 1e4，w_j ≤ 1e4（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

本题切入点

装箱最大化件数：把集装箱容量与货物重量都升序排序，双指针从小往大装（容量小的箱优先、能装就装），贪心可得最大件数。

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

  1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
  2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
  3. 按策略一次扫描（通常要先排序）得到答案。
  4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做（典型错因）。
  • 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

  • 数据规模 N ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：8 / 50 50 1 14 32 15 2 22 / 11 / 88 42 14 25 14 9 40 35 50 17 32
  • 输出：6

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-10月10号留学生开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解