🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C卷的三语言AC题解
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
文章目录
- 前言
- 🧭 机试备考指南
- 💊 传递悄悄话的最长时间
- 题目描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 🍓 AC代码截图 ✅
前言
🧭 机试备考指南
-
华为OD的题库大半年跟新一次,也就是说,一旦跟新,那么本年用的题目就是从该题库种选题,大概有100~200道左右
-
最近考试换为C/D卷,C/D卷题库是一样的,D卷为双机位监控,某些外包公司应聘的为D卷。
-
为此清隆帮大家搜集并整理了C卷的题库,后续会由清隆的ACM银牌团队将题目整理后搬上OJ,支持在线评测。
💊 传递悄悄话的最长时间
题目描述
在一个大家庭的聚会上,家庭成员站在由二叉树形式组织的位置上。每个位置上有一人,每个人之间的连接代表一条传递悄悄话的路径,且这条路径上有一个时间消耗。现在,根位置的K小姐想将一个悄悄话传递给所有人。每个连接的数字表示K小姐传递悄悄话给该节点的人所需额外时间。请计算使得所有家庭成员都听到这个悄悄话所需的最长时间。
输入格式
输入包含一行,由空格隔开的整数序列。这个序列以层序遍历的方式描述了一个二叉树,其中 -1
表示空节点。序列的第一个数字是根节点,表示从K小姐开始的时间为0。
输出格式
输出一个整数,表示所有节点都接收到悄悄话的最长时间。
样例输入
0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
样例输出
38
数据范围
输入的二叉树节点个数不超过 1000 1000 1000,时间都是非负整数,不超过 100 100 100。
题解
这个题目的核心是对二叉树进行遍历,并计算从根节点到每一个节点的路径时间。由于使用的是层序遍历的输入方式,我们可以使用队列来帮助我们构造这个二叉树,并同时计算从根节点到其他节点的时间。我们需要追踪的是从根节点到每个节点的累计时间,最终输出最大的那个时间,即为所有人都接收到悄悄话的最长时间。
参考代码
- 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 Queueinput_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 = 0while not q.empty():index, curr_time = q.get()max_time = max(max_time, curr_time)left_child_index = 2 * index + 1right_child_index = 2 * index + 2if 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;}}
}
🍓 AC代码截图 ✅
- Python