目录

题目

思路

Code

题目

在通信系统中，有一组数据包需要按顺序通过 k 个通道传输。每个数据包 i 的传输耗时为 nums[i]（单位：毫秒）。

传输规则：

第1点：同一通道内的数据包必须按顺序连续传输，即若数据包 [i, i+1, ..., j] 分配给同一通道，则该通道的传输总延迟为 nums[i] + nums[i+1] + ... + nums[j]。

第2点：不同通道之间可以并行传输，系统整体延迟取决于延迟最大的那个通道。

第3点：数据包只能被拆分为连续子段，例如 [1,2,3] 可以拆分为 [1,2]、[3]，不能拆分为 [1,3]、[2]。

任务：将 nums 数组划分到 k 个连续非空通道，使得传输总耗时最小。

输入描述

nums：非负整数数组，长度 n，1 <= n <= 1000，每个元素满足 0 <= nums[j] <= 10^6。

k：整数，通道数量，1 <= k <= n。

输入分两行：

nums

k

输出描述

返回一个整数，表示符合题意的最优传输策略下的总耗时。

样例 1

输入：

7,2,5,10,8

2

输出：

18

说明：划分为 [7,2,5] 和 [10,8] 时，两个通道耗时分别为 14 和 18，最大值为 18，是所有划分中的最小最大延迟。

样例 2

输入：

1,2,3,4,5

2

输出：

9

说明：最优划分为 [1,2,3] 和 [4,5]，总耗时为 9。

样例 3

输入：

1,4,4

3

输出：

4

说明：划分为 [1]、[4]、[4]，最优总耗时为 4。

思路

二分法

把最终答案看成一个最大延迟上限。给定某个上限后，从左到右尽量把数据包放进当前通道；如果加入当前包会超过上限，就新开一个通道。

这样得到的是该上限下所需的最少通道数。若通道数不超过 `k`，说明上限可行，可以继续尝试更小值；否则需要增大上限。

答案在“最大单个包耗时”和“全部包耗时之和”之间二分。

Code

nums = list(map(int, input().strip().split(",")))
# 读取数据包耗时数组和可用通道数 k。
k = int(input().strip())

# 给定上限 limit 后，贪心计算最少需要多少个连续通道。
def ok(limit):
    used, cur = 1, 0
    for x in nums:
        # 当前通道放不下时，开启新通道。
        if cur + x > limit:
            used += 1
            cur = x
        else:
            cur += x
    return used <= k

# 二分左边界是最大单包耗时，右边界是所有包耗时总和。
left, right = max(nums), sum(nums)
while left < right:
    mid = (left + right) // 2
    if ok(mid):
        right = mid
    else:
        left = mid + 1
# 二分结束时 left 就是最小可行最大延迟。
print(left)

JS

const fs = require("fs");

// 读取数据包耗时数组和可用通道数 k。
const lines = fs.readFileSync(0, "utf8").trim().split(/\n/);
const nums = lines[0].split(",").map(Number);
const k = Number(lines[1]);

function ok(limit) {
  let used = 1, cur = 0;
  // 给定上限 limit 后，贪心计算最少需要多少个连续通道。
  for (const x of nums) {
    // 放不下当前数据包时开启新通道。
    if (cur + x > limit) {
      // 通道数不超过 k 说明上限可行，可以继续缩小答案。
      used++;
      cur = x;
    } else {
      cur += x;
    }
  }
  return used <= k;
}

let left = Math.max(...nums);
let right = nums.reduce((a, b) => a + b, 0);
while (left < right) {
  const mid = Math.floor((left + right) / 2);
  if (ok(mid)) right = mid;
  else left = mid + 1;
}
// 二分结束时 left 就是最小可行最大延迟。
console.log(left);

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。