2024年华为OD机试真题-寻找最富裕的小家庭
华为OD机试真题-寻找最富裕的小家庭-2024年OD统一考试(D卷)
题目描述:
在一棵树中,每个节点代表一个家庭成员,节点的数字表示其个人的财富值,一个节点及其直接相连的子节点被定义为一个小家庭。
现给你一棵树,请计算出最富裕的小家庭的财富和。
输入描述:第一行为一个数N,表示成员总数,成员编号1-N,1<=N<=1000
第二行为N个空格分隔的数,表示编号1-N的成员的财富值。0<=财富值<=1000000
接下来N-1行,每行两个空格分隔的整数(N1,N2),表示N1是N2的父节点。
输出描述:
最富裕的小家庭的财富和
补充说明:
收起
示例1
输入:
4 100 200 300 500 1 2 1 3 2 4输出:
700说明:
成员1,2,3组成的小家庭财富值为600
成员2,4组成的小家庭财富值为700
示例2
输入:
4 100 200 300 500 1 2 1 3 1 4输出:
1100说明:
成员1,2,3,4组成的小家庭财富值为1100
解题思路:
很简单循环和逻辑判断解题。
Java解法:
import java.util.ArrayList; import java.util.HashMap; import java.util.Map.Entry; import java.util.List; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextLine()) { / int N = Integer.parseInt(in.nextLine()); String moneys = in.nextLine(); List<Integer> moneyList = new ArrayList<>(); for(String money : moneys.split(" ")){ moneyList.add(Integer.parseInt(money)); } Map<Integer, List<Integer>> familyMap = new HashMap<>(); for(int i = 0;i < N-1; i++){ String line = in.nextLine(); int parent = Integer.parseInt(line.split(" ")[0]); int son = Integer.parseInt(line.split(" ")[1]); List<Integer> sons = null; if(familyMap.containsKey(parent)){ sons = familyMap.get(parent); } else { sons = new ArrayList<>(); } sons.add(son); familyMap.put(parent,sons); } int maxMoney = 0; for(Entry<Integer, List<Integer>> entry : familyMap.entrySet()){ List<Integer> sonList = entry.getValue(); int parent = entry.getKey(); int moneyCn = moneyList.get(parent-1); for(int son : sonList){ moneyCn += moneyList.get(son-1); } if(moneyCn > maxMoney){ maxMoney = moneyCn; } } System.out.println(maxMoney); } } }
Python解法:
from os import linesep import sys num = int(sys.stdin.readline().strip()) data = sys.stdin.readline().strip().split(' ') data = [int(elem) for elem in data] dependency = {} while True: line = sys.stdin.readline() if line == '': break else: relation = line.strip().split(' ') if relation[0] in dependency.keys(): dependency[relation[0]].append(relation[-1]) else: dependency[relation[0]] = [relation[-1]] value = [] for key in dependency.keys(): value.append(data[int(key)-1]) for member in dependency[key]: value[-1] += data[int(member)-1] if len(value) == 1: print(value[-1]) else: print(max(value))
C++解法:
#include <cstddef> #include <iostream> using namespace std; #include <map> #include <vector> #include <cmath> int main() { int N; cin >> N; vector<int> val(N + 1, 0); int i = 0; while (i < N) { cin >> val[i + 1]; i++; } i = 0; map<int, vector<int>> mp; while (i < N - 1) { int x1, x2; cin >> x1 >> x2; if (mp.find(x1) != mp.end()) { mp[x1].push_back(x2); } else { vector<int> v; v.push_back(x2); mp.insert(make_pair(x1, v)); } i++; } int res = 0; auto it = mp.begin(); while (it != mp.end()) { int acc = val[it->first]; for (int i = 0; i < (it->second).size(); i++) { acc += val[(it->second)[i]]; } if (res < acc) res = acc; it++; } cout << res << endl; return 0; }
欢迎交流指正~
#华为od##华为#华为OD机试题库2024年 文章被收录于专栏
2024年OD统一考试(D卷),最新最完整题库。 收录130+道真题,提供解题思路,Java/Python/C++三种答案源码。