最新华为OD机试真题-传递悄悄话的最长时间(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 传递悄悄话的最长时间(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🚅 传递悄悄话的最长时间

题目描述

在一个大家庭的聚会上，家庭成员站在由二叉树形式组织的位置上。每个位置上有一人，每个人之间的连接代表一条传递悄悄话的路径，且这条路径上有一个时间消耗。现在，根位置的K小姐想将一个悄悄话传递给所有人。每个连接的数字表示K小姐传递悄悄话给该节点的人所需额外时间。请计算使得所有家庭成员都听到这个悄悄话所需的最长时间。

输入格式

输入包含一行，由空格隔开的整数序列。这个序列以层序遍历的方式描述了一个二叉树，其中 -1 表示空节点。序列的第一个数字是根节点，表示从K小姐开始的时间为0。

输出格式

输出一个整数，表示所有节点都接收到悄悄话的最长时间。

样例输入

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

样例输出

38

数据范围

输入的二叉树节点个数不超过 ，时间都是非负整数，不超过 。

题解

这个题目的核心是对二叉树进行遍历，并计算从根节点到每一个节点的路径时间。由于使用的是层序遍历的输入方式，我们可以使用队列来帮助我们构造这个二叉树，并同时计算从根节点到其他节点的时间。我们需要追踪的是从根节点到每个节点的累计时间，最终输出最大的那个时间，即为所有人都接收到悄悄话的最长时间。

参考代码

• Cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<int> input;
    int tmp;
    while (cin >> tmp) {
        input.push_back(tmp);
    }

    if (input.empty() || input[0] == -1) {
        cout << "0" << endl;
        return 0;
    }

    queue<pair<int, int>> q; // pair<index, time>
    q.push({0, input[0]});
    int maxTime = 0;

    while (!q.empty()) {
        auto [index, currTime] = q.front();
        q.pop();
        maxTime = max(maxTime, currTime);

        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;

        if (leftChildIndex < input.size() && input[leftChildIndex] != -1) {
            q.push({leftChildIndex, currTime + input[leftChildIndex]});
        }
        if (rightChildIndex < input.size() && input[rightChildIndex] != -1) {
            q.push({rightChildIndex, currTime + input[rightChildIndex]});
        }
    }

    cout << maxTime << endl;
    return 0;
}

• Python

from queue import Queue

input_str = input().split()
input = [int(x) if x != '-1' else -1 for x in input_str]

if not input or input[0] == -1:
    print("0")
    exit()

q = Queue()
q.put((0, input[0]))
max_time = 0

while not q.empty():
    index, curr_time = q.get()
    max_time = max(max_time, curr_time)

    left_child_index = 2 * index + 1
    right_child_index = 2 * index + 2

    if left_child_index < len(input) and input[left_child_index] != -1:
        q.put((left_child_index, curr_time + input[left_child_index]))
    if right_child_index < len(input) and input[right_child_index] != -1:
        q.put((right_child_index, curr_time + input[right_child_index]))

print(max_time)

• Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class MaxSumPath {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] inputStr = scanner.nextLine().split(" ");
        int[] input = new int[inputStr.length];
        for (int i = 0; i < inputStr.length; i++) {
            input[i] = Integer.parseInt(inputStr[i]);
        }

        if (input.length == 0 || input[0] == -1) {
            System.out.println("0");
            return;
        }

        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(0, input[0]));
        int maxTime = 0;

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            int index = pair.index;
            int currTime = pair.time;
            maxTime = Math.max(maxTime, currTime);

            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;

            if (leftChildIndex < input.length && input[leftChildIndex] != -1) {
                queue.add(new Pair(leftChildIndex, currTime + input[leftChildIndex]));
            }
            if (rightChildIndex < input.length && input[rightChildIndex] != -1) {
                queue.add(new Pair(rightChildIndex, currTime + input[rightChildIndex]));
            }
        }

        System.out.println(maxTime);
    }

    static class Pair {
        int index;
        int time;

        Pair(int index, int time) {
            this.index = index;
            this.time = time;
        }
    }
}