数据包分段传输的最小最大延迟

2026 华为OD机试真题 6月22日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

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

传输规则

  • 同一通道内的数据包必须按顺序连续传输，即若数据包 [i, i+1, …, j] 分配给同一通道，则该通道的传输总延迟为 nums[i]+nums[i+1]+…+nums[j]。
  • 不同通道之间可以并行传输，系统整体延迟取决于延迟最大的那个通道。
  • 数据包只能被拆分为连续子段，例如 [1, 2, 3] 可以被拆分为 [1, 2], [3]，但是不能被拆分为 [1, 3], [2]。

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

输入描述

  • nums：非负整数数组，长度 n（1≤n≤1000），每个元素满足 0≤nums[j]≤106。
  • k：整数，通道数量（1≤k≤n）。

输出描述

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

示例1

输入

7,2,5,10,8
2

输出

18

说明

输入: nums=[7, 2, 5, 10, 8], k=2 输出: 18 解释: 共有以下划分方案（划分为2个连续子数组）： 方案1: [7], [2,5,10,8]→ 总耗时为 25 方案2: [7,2], [5,10,8]→ 总耗时为 23 方案3: [7,2,5], [10,8]→ 总耗时为 18← 最优 方案4: [7,2,5,10], [8]→ 总耗时为 24 因此最优总耗时为 18。

示例2

输入

[1, 2, 3, 4, 5],2

输出

9

说明

输入: nums=[1, 2, 3, 4, 5], k=2 输出: 9 解释: 最优划分为 [1,2,3] 和 [4,5]，最优总耗时为 9。

示例3

输入

1, 4, 4
3

输出

4

说明

输入: nums=[1, 4, 4], k=3 输出: 4 解释: 划分为 [1], [4], [4]，最优总耗时为 4。

解题思路

本题要求将数组划分为 k 个连续非空子段，使得所有子段和的最大值最小。这是一个经典的「分割数组/划分问题」，常使用二分查找 + 贪心验证策略求解。

关键洞察：

  • 如果某个阈值 limit 可行（能将数组划分为不超过 k 个子段，且每个子段和 ≤ limit），那么所有更大的阈值也一定可行。
  • 如果某个阈值 limit 不可行，那么所有更小的阈值也一定不可行。
  • 这种单调性使得我们可以使用二分查找找到最小的可行阈值。

算法流程：

  1. 确定搜索范围：下界为数组中的最大值（每个数据包必须单独传输），上界为数组所有元素之和（所有数据包在一个通道）。
  2. 二分查找：对于每个候选阈值 mid，使用贪心算法检查能否将数组划分为不超过 k 个子段。
  3. 贪心验证：遍历数组，尽量在当前段中添加元素，如果添加后超过 mid，则开启新段。最终统计所需段数是否 ≤ k。

复杂度分析

  • 时间复杂度：O(n × log(sum))，其中 n 是数组长度，sum 是数组元素之和。二分查找 log(sum) 次，每次验证 O(n)。
  • 空间复杂度：O(1)，只使用了常数额外空间。

Java

import java.util.Scanner;

public class Main {
    // 检查在给定的最大延迟限制下，是否能将数据包划分为不超过 k 个通道
    private static boolean canSplit(int[] packets, long limit, int k) {
        int segments = 1;       // 当前使用的通道数
        long currentSum = 0;     // 当前通道的累计延迟

        for (int packet : packets) {
            // 如果当前通道加上这个数据包会超过限制，则开启新通道
            if (currentSum + packet > limit) {
                segments++;          // 新增一个通道
                currentSum = 0;      // 重置当前通道累计延迟
            }
            currentSum += packet;    // 将数据包加入当前通道
        }
        // 所需通道数不超过 k 则该 limit 可行
        return segments <= k;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取第一行：数据包大小数组
        String line = scanner.nextLine().trim();
        // 解析数组，处理 [ ] 和空格
        line = line.replaceAll("[\\[\\] ]", "");
        String[] parts = line.split(",");
        int n = parts.length;
        int[] packets = new int[n];
        for (int i = 0; i < n; i++) {
            packets[i] = Integer.parseInt(parts[i]);
        }

        // 读取第二行：通道数量
        int k = Integer.parseInt(scanner.nextLine().trim());

        // 二分查找求解最小最大延迟
        int left = 0, right = 0;
        for (int packet : packets) {
            left = Math.max(left, packet);  // 下界：单个最大数据包
            right += packet;                 // 上界：所有数据包之和
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(packets, mid, k)) {
                right = mid;  // mid 可行，尝试更小的限制
            } else {
                left = mid + 1;  // mid 不可行，需要增大限制
            }
        }

        System.out.println(left);
        scanner.close();
    }
}

Python

import sys

def can_split(packets, limit, k):
    """
    贪心验证：检查在给定的最大延迟限制下，是否能将数据包划分为不超过 k 个通道

    参数:
        packets: 数据包大小列表
        limit: 允许的单通道最大延迟
        k: 可用的通道数量

    返回:
        bool: 如果能够划分为不超过 k 个通道则返回 True
    """
    segments = 1      # 当前划分的段数（至少1段）
    current_sum = 0   # 当前段的累计延迟

    for packet in packets:
        # 如果当前段加上此数据包会超过限制，则开启新段
        if current_sum + packet > limit:
            segments += 1
            current_sum = 0
        current_sum += packet

    return segments <= k

def minimum_latency(packets, k):
    """
    二分查找求解：将数组划分为 k 个连续子段，使得最大子段和最小

    参数:
        packets: 数据包大小列表
        k: 要划分的段数

    返回:
        int: 最小的最大延迟
    """
    # 确定搜索范围
    left = max(packets)   # 下界：必须至少能容纳最大的数据包
    right = sum(packets)  # 上界：所有数据包放在一个通道

    while left < right:
        mid = (left + right) // 2
        if can_split(packets, mid, k):
            right = mid   # mid 可行，尝试更小的值
        else:
            left = mid + 1 # mid 不可行，需要增大

    return left

def main():
    lines = [line.strip() for line in sys.stdin if line.strip()]
    if not lines:
        return

    # 解析第一行：数据包数组
    nums_str = lines[0].replace('[', '').replace(']', '').replace(' ', '')
    packets = list(map(int, nums_str.split(',')))

    # 解析第二行：通道数量
    k = int(lines[1])

    result = minimum_latency(packets, k)
    print(result)

if __name__ == "__main__":
    main()

JavaScript

 const readline = require('readline');

function can_split(packets, limit, k) {
    /*
     * 贪心验证：检查在给定的最大延迟限制下，是否能将数据包划分为不超过 k 个通道
     */
    let segments = 1;
    let current_sum = 0;

    for (const packet of packets) {
        if (current_sum + packet > limit) {
            segments += 1;
            current_sum = 0;
        }
        current_sum += packet;
    }

    return segments <= k;
}

function minimum_latency(packets, k) {
    /*
     * 二分查找求解：将数组划分为 k 个连续子段，使得最大子段和最小
     */
    let left = Math.max(...packets);
    let right = packets.reduce((sum, x) => sum + x, 0);

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (can_split(packets, mid, k)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

function main() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    const lines = [];

    rl.on('line', (line) => {
        const trimmed = line.trim();
        if (trimmed) {
            lines.push(trimmed);
        }
    });

    rl.on('close', () => {
        if (lines.length === 0) {
            return;
        }

        const nums_str = lines[0].replace(/\[/g, '').replace(/\]/g, '').replace(/\s/g, '');
        const packets = nums_str.split(',').map(Number);

        const k = Number(lines[1]);

        const result = minimum_latency(packets, k);
        console.log(result);
    });
}

main();

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

// 贪心验证：检查在给定的最大延迟限制下，是否能将数据包划分为不超过 k 个通道
bool canSplit(const vector<int>& packets, long long limit, int k) {
    int segments = 1;           // 当前划分的段数（至少1段）
    long long currentSum = 0;   // 当前段的累计延迟

    for (int packet : packets) {
        // 如果当前段加上此数据包会超过限制，则开启新段
        if (currentSum + packet > limit) {
            segments++;
            currentSum = 0;
        }
        currentSum += packet;
    }

    return segments <= k;
}

// 二分查找求解最小最大延迟
int minimumLatency(vector<int>& packets, int k) {
    // 确定搜索范围
    int left = *max_element(packets.begin(), packets.end());  // 下界：最大数据包
    int right = 0;
    for (int p : packets) right += p;  // 上界：所有数据包之和

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canSplit(packets, mid, k)) {
            right = mid;   // mid 可行，尝试更小的值
        } else {
            left = mid + 1; // mid 不可行，需要增大
        }
    }

    return left;
}

// 解析输入字符串，提取数字数组
vector<int> parseArray(const string& str) {
    vector<int> result;
    string s = str;
    // 移除括号和空格
    s.erase(remove(s.begin(), s.end(), '['), s.end());
    s.erase(remove(s.begin(), s.end(), ']'), s.end());
    s.erase(remove(s.begin(), s.end(), ' '), s.end());

    stringstream ss(s);
    string token;
    while (getline(ss, token, ',')) {
        if (!token.empty()) {
            result.push_back(stoi(token));
        }
    }
    return result;
}

int main() {
    string line1, line2;

    // 读取第一行：数据包数组
    getline(cin, line1);
    // 读取第二行：通道数量
    getline(cin, line2);

    // 解析输入
    vector<int> packets = parseArray(line1);
    int k = stoi(line2);

    // 计算并输出结果
    int result = minimumLatency(packets, k);
    cout << result << endl;

    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// canSplit 贪心验证：检查在给定的最大延迟限制下，是否能将数据包划分为不超过 k 个通道
func canSplit(packets []int, limit int, k int) bool {
	segments := 1        // 当前划分的段数（至少1段）
	currentSum := 0     // 当前段的累计延迟

	for _, packet := range packets {
		// 如果当前段加上此数据包会超过限制，则开启新段
		if currentSum+packet > limit {
			segments++
			currentSum = 0
		}
		currentSum += packet
	}

	return segments <= k
}

// minimumLatency 二分查找求解：将数组划分为 k 个连续子段，使得最大子段和最小
func minimumLatency(packets []int, k int) int {
	// 确定搜索范围
	left := packets[0]
	right := 0
	for _, p := range packets {
		if p > left {
			left = p
		}
		right += p
	}

	for left < right {
		mid := (left + right) / 2
		if canSplit(packets, mid, k) {
			right = mid // mid 可行，尝试更小的值
		} else {
			left = mid + 1 // mid 不可行，需要增大
		}
	}

	return left
}

// parseArray 解析输入字符串，提取数字数组
func parseArray(s string) []int {
	// 移除括号和空格
	s = strings.ReplaceAll(s, "[", "")
	s = strings.ReplaceAll(s, "]", "")
	s = strings.ReplaceAll(s, " ", "")

	parts := strings.Split(s, ",")
	result := make([]int, 0, len(parts))
	for _, part := range parts {
		if part == "" {
			continue
		}
		num, err := strconv.Atoi(part)
		if err == nil {
			result = append(result, num)
		}
	}
	return result
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	// 读取第一行：数据包数组
	var line1, line2 string
	if scanner.Scan() {
		line1 = scanner.Text()
	}
	// 读取第二行：通道数量
	if scanner.Scan() {
		line2 = scanner.Text()
	}

	// 解析输入
	packets := parseArray(strings.TrimSpace(line1))
	k, _ := strconv.Atoi(strings.TrimSpace(line2))

	// 计算并输出结果
	result := minimumLatency(packets, k)
	fmt.Println(result)
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_LEN 10000

// 贪心验证：检查在给定的最大延迟限制下，是否能将数据包划分为不超过 k 个通道
int canSplit(int* packets, int n, int limit, int k) {
    int segments = 1;       // 当前划分的段数（至少1段）
    int currentSum = 0;    // 当前段的累计延迟

    for (int i = 0; i < n; i++) {
        // 如果当前段加上此数据包会超过限制，则开启新段
        if (currentSum + packets[i] > limit) {
            segments++;
            currentSum = 0;
        }
        currentSum += packets[i];
    }

    return segments <= k;
}

// 二分查找求解最小最大延迟
int minimumLatency(int* packets, int n, int k) {
    // 确定搜索范围
    int left = packets[0];
    int right = 0;
    for (int i = 0; i < n; i++) {
        if (packets[i] > left) {
            left = packets[i];
        }
        right += packets[i];
    }

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canSplit(packets, n, mid, k)) {
            right = mid;   // mid 可行，尝试更小的值
        } else {
            left = mid + 1; // mid 不可行，需要增大
        }
    }

    return left;
}

// 解析输入字符串，提取数字数组
int parseArray(const char* str, int* packets) {
    char s[MAX_LEN];
    strcpy(s, str);

    // 移除括号和空格
    char* src = s;
    char* dst = s;
    while (*src) {
        if (*src != '[' && *src != ']' && *src != ' ') {
            *dst++ = *src;
        }
        src++;
    }
    *dst = '\0';

    int count = 0;
    char* token = strtok(s, ",");
    while (token != NULL) {
        packets[count++] = atoi(token);
        token = strtok(NULL, ",");
    }
    return count;
}

int main() {
    char line1[MAX_LEN];
    char line2[MAX_LEN];

    // 读取第一行：数据包数组
    fgets(line1, MAX_LEN, stdin);
    line1[strcspn(line1, "\n")] = 0;

    // 读取第二行：通道数量
    fgets(line2, MAX_LEN, stdin);
    line2[strcspn(line2, "\n")] = 0;

    // 解析输入
    int packets[MAX_LEN];
    int n = parseArray(line1, packets);
    int k = atoi(line2);

    // 计算并输出结果
    int result = minimumLatency(packets, n, k);
    printf("%d\n", result);

    return 0;
}

完整用例

用例1

7,2,5,10,8
2

用例2

1, 2, 3, 4, 5
2

用例3

1, 4, 4
3

用例4

10,20,30,40
1

用例5

5,5,5,5
4

用例6

3,1,2,7,4,6
3

用例7

100,200,150,300
2

用例8

1,1,1,1,1,1
2

用例9

5,10,15,20,25,30
3

用例10

0,5,0,10,0
3

文章目录

在这里插入图片描述

# java # c语言
Logo
亚马逊云科技技术品牌专区

更多推荐

2026年量化工具选择，要跟着能力基础走

读者应理解，选择工具前要先判断自己的能力基础和当前任务。工具应该帮助自己补上当前最关键的缺口，而不是替代学习顺序本身。

avatar 亚马逊云科技技术品牌专区

近期零基础学量化，先按基础差异拆学习顺序

读者应明白，拆解学习顺序时要先看自己的基础缺口，再决定哪一段需要放慢。不同流程阶段都有不同检查任务，学习路线要能反映这些差异。

avatar 亚马逊云科技技术品牌专区

加州理工 CS367 C 语言系统编程笔记（一）

C语言是一种强大且广泛使用的编程语言，尤其在系统编程领域。本节课我们将学习C语言的基础语法，包括如何编写“Hello, World!”程序、声明变量以及使用基本数据类型。我们将通过实际的代码示例来加深理解。本节课中我们一起学习了C语言的基础语法，包括如何编写和运行一个简单的C程序、声明变量以及使用基本数据类型。我们还介绍了如何使用Shell环境来编译和运行程序。通过对比Java，你可以看到C语言在

avatar 亚马逊云科技技术品牌专区