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

题目描述

一个云计算平台需要调度一批数据处理任务。每个任务都有一个计算成本,由一个正整数数组 costs 表示,其中 costs[i] 代表第 i 个任务的计算成本。
平台拥有一批计算能力相同的服务器,每台服务器的最大计算容量为 C 。为了优化资源利用率,任务分配遵循一种贪心策略:调度器为一台服务器分配任务时,总是优先选择当前未分配的、计算成本最高的,且不会超出服务器剩余容量的任务。
你需要计算,要处理完所有任务,最少需要多少台服务器。

输入输出

输入描述
第一行:一个正整数 N ,表示任务的总数,其中 1 ≤ N ≤ 10^4 。
第二行:一个包含 N 个正整数的数组 costs ,表示每个任务的计算成本,其中 1 ≤ costs[i] ≤ 10^4 。
第三行:一个正整数 C ,表示每台服务器的最大计算容量,其中 1 ≤ C ≤ 10^4 。
输出描述
输出一个整数,代表处理所有任务所需的最少服务器数量。

样例共 1 组

样例 1
输入
13
78 32 44 98 73 46 98 31 54 27 51 9 8
113
输出
7

算法解析依据一般

考点:贪心

数据规模 N ≤ 1e4 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:N ≤ 1e4
  • 元素值域:costs[i] ≤ 1e4,C ≤ 1e4(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:贪心

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

思路框架(贪心 通法 · 非本题专属)

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

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

复杂度:时间 O(n log n)(含排序) | 空间 O(1) ~ O(n)

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 1e4,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:13 / 78 32 44 98 73 46 98 31 54 27 51 9 8 / 113
  • 输出:7

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

本题来源:2025年秋招-华为-9月28号开发岗。

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