华为OD机试新系统真题【数据包分段传输的最小最大延迟】

# 数据包分段传输的最小最大延迟(C/C++/Py/Java/Js/Go)题解

华为OD机试新系统真题 华为OD上机考试新系统真题 6月21号 200分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

在通信系统中，有一组数据包需要按顺序通过

k

k

k 个通道传输。每个数据包

i

i

i 的传输耗时为

n

u

m

s

[

i

]

nums[i]

nums[i]（单位：毫秒）。

传输规则:

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

输入描述

• $nums$
• $k$

输出描述

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

样例1

输入

7,2,5,10,8
2

输出

18

说明 输入:

n

u

m

s

=

[

7

,

2

,

5

,

10

,

8

]

,

k

=

2

nums = [7,\\ 2,\\ 5,\\ 10,\\ 8],\\ k = 2

nums=[7, 2, 5, 10, 8], k=2 输出:

18

18

18 解释: 共有以下划分方案（划分为

2

2

2个连续子数组）： 方案1:

[

7

]

,

[

2

,

5

,

10

,

8

]

→

[7],\\ [2,5,10,8] \\to

[7], [2,5,10,8]→ 总耗时为

25

25

25 方案2:

[

7

,

2

]

,

[

5

,

10

,

8

]

→

[7,2],\\ [5,10,8] \\to

[7,2], [5,10,8]→ 总耗时为

23

23

23 方案3:

[

7

,

2

,

5

]

,

[

10

,

8

]

→

[7,2,5],\\ [10,8] \\to

[7,2,5], [10,8]→ 总耗时为

18

←

18 \\leftarrow

18← 最优 方案4:

[

7

,

2

,

5

,

10

]

,

[

8

]

→

[7,2,5,10],\\ [8] \\to

[7,2,5,10], [8]→ 总耗时为

24

24

24 因此最优总耗时为

18

18

18。

样例2

输入

1,2,3,4,5
2

输出

9

说明 输入:

n

u

m

s

=

[

1

,

2

,

3

,

4

,

5

]

,

k

=

2

nums = [1,\\ 2,\\ 3,\\ 4,\\ 5],\\ k = 2

nums=[1, 2, 3, 4, 5], k=2 输出:

9

9

9 解释: 最优划分为

[

1

,

2

,

3

]

[1,2,3]

[1,2,3] 和

[

4

,

5

]

[4,5]

[4,5]，最优总耗时为

9

9

9。

样例3

输入

1,4,4
3

输出

4

说明 输入:

n

u

m

s

=

[

1

,

4

,

4

]

,

k

=

3

nums = [1,\\ 4,\\ 4],\\ k = 3

nums=[1, 4, 4], k=3 输出:

4

4

4 解释: 划分为

[

1

]

,

[

4

]

,

[

4

]

[1],\\ [4],\\ [4]

[1], [4], [4]，最优总耗时为

4

4

4。

题解

思路：二分

C++

#include<bits/stdc++.h>
#include <vector>
using namespace std;

// 通用 切割函数 函数 将字符串str根据delimiter进行切割
vector<int> split(const string& str, const string& delimiter) {
vector<int> result;
size_t start = 0;
size_t end = str.find(delimiter);
while (end != string::npos) {
result.push_back(stoi(str.substr(start, end – start)));
start = end + delimiter.length();
end = str.find(delimiter, start);
}
// 添加最后一个部分
result.push_back(stoi(str.substr(start)));
return result;
}

// 检验指定每个通道最大延迟限制下所需通道数是否小于等于k
bool judge(vector<int>& nums, int k, int mid) {
// 所需通道数
int cnt = 1;
int sum =0;
int n = nums.size();
for (auto& val : nums) {
if (val + sum > mid) {
cnt++;
sum = 0;
}
sum += val;
}
return cnt <= k;
}

int getminniDelay(vector<int>& nums, int k) {
// 上下边界 下边界为最大耗时
int left = 0;
// 上边界为耗时和
int right = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
left = max(left, nums[i]);
right += nums[i];
}
while (left < right) {
int mid = (left + right) >> 1;
if (judge(nums, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

int main() {
string input;
getline(cin, input);
vector<int> nums = split(input, ",");
int k;
cin >> k;
cout << getminniDelay(nums, k);
return 0;
}

JAVA

import java.io.*;
import java.util.*;

public class Main {

// 检验指定每个通道最大延迟限制下所需通道数是否小于等于k
static boolean judge(int[] nums, int k, int mid) {
// 所需通道数
int cnt = 1;
int sum = 0;

for (int val : nums) {
if (val + sum > mid) {
cnt++;
sum = 0;
}
sum += val;
}

return cnt <= k;
}

static int getminniDelay(int[] nums, int k) {
// 上下边界 下边界为最大耗时
int left = 0;

// 上边界为耗时和
int right = 0;

for (int num : nums) {
left = Math.max(left, num);
right += num;
}

while (left < right) {
int mid = (left + right) >> 1;

if (judge(nums, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}

return left;
}

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input = br.readLine();

String[] parts = input.split(",");

int[] nums = new int[parts.length];

for (int i = 0; i < parts.length; i++) {
nums[i] = Integer.parseInt(parts[i]);
}

int k = Integer.parseInt(br.readLine());

System.out.println(getminniDelay(nums, k));
}
}

Python

# 检验指定每个通道最大延迟限制下所需通道数是否小于等于k
def judge(nums, k, mid):
# 所需通道数
cnt = 1
total = 0

for val in nums:
if val + total > mid:
cnt += 1
total = 0

total += val

return cnt <= k

def getminni_delay(nums, k):
# 上下边界 下边界为最大耗时
left = max(nums)

# 上边界为耗时和
right = sum(nums)

while left < right:
mid = (left + right) >> 1

if judge(nums, k, mid):
right = mid
else:
left = mid + 1

return left

nums = list(map(int, input().split(",")))
k = int(input())

print(getminni_delay(nums, k))

JavaScript

const readline = require("readline");

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

const lines = [];

rl.on("line", line => {
lines.push(line);
});

rl.on("close", () => {

const nums = lines[0].split(",").map(Number);
const k = Number(lines[1]);

// 检验指定每个通道最大延迟限制下所需通道数是否小于等于k
function judge(nums, k, mid) {
// 所需通道数
let cnt = 1;
let sum = 0;

for (const val of nums) {
if (val + sum > mid) {
cnt++;
sum = 0;
}

sum += val;
}

return cnt <= k;
}

function getminniDelay(nums, k) {

// 上下边界 下边界为最大耗时
let left = 0;

// 上边界为耗时和
let right = 0;

for (const num of nums) {
left = Math.max(left, num);
right += num;
}

while (left < right) {
const mid = (left + right) >> 1;

if (judge(nums, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}

return left;
}

console.log(getminniDelay(nums, k));
});

Go

package main

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

// 检验指定每个通道最大延迟限制下所需通道数是否小于等于k
func judge(nums []int, k int, mid int) bool {
// 所需通道数
cnt := 1
sum := 0

for _, val := range nums {
if val+sum > mid {
cnt++
sum = 0
}

sum += val
}

return cnt <= k
}

func getminniDelay(nums []int, k int) int {
// 上下边界 下边界为最大耗时
left := 0

// 上边界为耗时和
right := 0

for _, num := range nums {
if num > left {
left = num
}
right += num
}

for left < right {
mid := (left + right) >> 1

if judge(nums, k, mid) {
right = mid
} else {
left = mid + 1
}
}

return left
}

func main() {
reader := bufio.NewReader(os.Stdin)

line, _ := reader.ReadString('\\n')
line = strings.TrimSpace(line)

parts := strings.Split(line, ",")

nums := make([]int, len(parts))

for i, s := range parts {
nums[i], _ = strconv.Atoi(s)
}

var k int
fmt.Fscan(reader, &k)

fmt.Println(getminniDelay(nums, k))
}

C语言

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

// 检验指定每个通道最大延迟限制下所需通道数是否小于等于k
int judge(int nums[], int n, int k, int mid) {

// 所需通道数
int cnt = 1;
int sum = 0;

for (int i = 0; i < n; i++) {

if (nums[i] + sum > mid) {
cnt++;
sum = 0;
}

sum += nums[i];
}

return cnt <= k;
}

int getminniDelay(int nums[], int n, int k) {

// 上下边界 下边界为最大耗时
int left = 0;

// 上边界为耗时和
int right = 0;

for (int i = 0; i < n; i++) {
if (nums[i] > left) {
left = nums[i];
}
right += nums[i];
}

while (left < right) {

int mid = (left + right) >> 1;

if (judge(nums, n, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}

return left;
}

int main() {

char input[100000];

fgets(input, sizeof(input), stdin);

input[strcspn(input, "\\n")] = '\\0';

int nums[1000];
int n = 0;

char *token = strtok(input, ",");

while (token != NULL) {
nums[n++] = atoi(token);
token = strtok(NULL, ",");
}

int k;
scanf("%d", &k);

printf("%d\\n", getminniDelay(nums, n, k));

return 0;
}

​