首页 > 试题广场 >

Shopee的Orange Day Shopee每个月

[问答题]
Shopee的Orange Day
Shopee每个月都有属于大家的节日，每到这个时候，大家都会穿着橙色的T恤，吃着水果蛋糕，做着游戏。瞧，今天又是Orange Day了，吃货小虾同学早早的来到现场，看看有没有什么吃的，刚刚走进去就发现我们的前台mm愁眉苦脸的看着挂满礼物的发财树，细看发现，发财树的树枝因为承重不均，东倒西歪。是时候展现真正的技术啦，小虾同学，马上走上去，让前台mm把挂礼物的方案拿出来，前台mm拿出一大叠方案，小虾同学顿时傻眼了，但是他马上想到了一个方法，写一个程序判断每种方案的承重误差，把不合格的都干掉就行了。经过分析，把发财树抽象为一颗树。只要发财树的从顶部到各个叶子的各个路径上面的最大最小重量的差值在方案的误差范围内，就可以正常承重。

输入第一行表示数据样例数T，表示接下来会有T个相同格式的样例输入

每个样例输入如下

输入的第一行输入 n,（2 ≤ n ≤ 100000，节点的编号为0到n-1,0为根节点）组成，

第二行有 n 个数，表示每个节点挂的礼物的重量 w（1<= w<= 1000）
下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

输出最大差值。

添加回答
JJJJJin头像 JJJJJin 
n = int(input())
w = list(map(int, input().split())) #输入每个节点的礼物重量
num = [list(map(int, input().split())) for i in range(n-1)] #输入父节点+子节点

for i in num:
    fa = i[0]
    son = i[1]
    weight = float('-inf')
    weight_tem = abs(w[fa] - w[son])
    if weight_tem > weight:
        weight = weight_tem

print(weight)


    


发表于 2020-07-20 22:16:11 回复(0)
呷脯呷脯头像 呷脯呷脯 
//参照kakifuu大佬的做法，我觉得他构建树的时候有点迷，没看明白，
//于是就借鉴了一下思路，利用回溯方法来做这道题，自己随便写了个测试用例至少是通过了
//望大佬们指正！

public class ChristmasTree {
    static int sum = 0;
    static int max = Integer.MIN_VALUE;
    static class Node{
        int val;
        List<Node> children;
        Node(int val){
            this.val = val;
            children = new ArrayList<>();
        }
        public void addChild(Node node){
            children.add(node);
        }
    }

    public static void dfs(Node node){
        sum += node.val;
        if(node.children.size()==0){
            max = Math.max(max,sum);
        }else{
            for(int i=0;i<node.children.size();i++){
                dfs(node.children.get(i));
            }
        }
        sum-=node.val;

    }

    public static void main(String[] args) {
        System.out.println("请输入节点总数：");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node[] nodes = new Node[n];
        System.out.println("请输入每个结点的重量：");
        for(int i=0;i<n;i++){
            int val = scanner.nextInt();
            nodes[i] = new Node(val);
        }

        //构建树
        System.out.println("请输入父子节点编号：");
        for(int i=0;i<n-1;i++){
            int parentNum = scanner.nextInt();
            int childNum = scanner.nextInt();
            nodes[parentNum].addChild(nodes[childNum]);
        }
        dfs(nodes[0]);
        System.out.println("最大重量为："+max);
    }
}


请输入节点总数：
5
请输入每个结点的重量：
5 3 7 8 1
请输入父子节点编号：
0 1
0 2
1 3
1 4
最大重量为：16


编辑于 2020-07-14 10:40:05 回复(0)
Slippers_头像 Slippers_ 
import java.util.*;

// 深度遍历，用栈实现

public class Main {

    static class point{
        int old, young;
        point(int old, int young){ this.old = old; this.young = young; }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t-- != 0){
            int n = in.nextInt();
            int[] weight = new int[n];
            for(int i = 0; i < n; i++) weight[i] = in.nextInt();
            Map<Integer, LinkedList<Integer>> map = new HashMap();
            for(int i = 0; i < n - 1; i++) {
                int tmpOld = in.nextInt(); int tmpYoung = in.nextInt();
                LinkedList<Integer> tmpList = map.get(tmpOld);
                if(tmpList == null) tmpList = new LinkedList<>();
                tmpList.add(tmpYoung);
                map.put(tmpOld, tmpList);
            }
            for(int i = 0; i < map.size(); i++){
                System.out.println(i + "  " + map.get(i).toString());
            }

            LinkedList<point> stack = new LinkedList<>();
            point p = new point(0, 0);
            // 深度遍历
            int max = 0;
            Vector<Integer> nums = new Vector<>();
            while(stack.size() != 0 || p != null){
                while(p != null){
                    stack.add(p);
                    nums.add(weight[p.young]);
                    int pYoung = p.young;
                    if(map.get(p.young) != null && map.get(p.young).size() != 0) {
                        p = new point(pYoung, map.get(pYoung).poll());
                    }
                    else p = null;
                }
                System.out.println("走到最底： " + nums.toString());
                Object[] numsArr = nums.toArray();
                Arrays.sort(numsArr);
                max = Math.max((Integer) numsArr[numsArr.length - 1] - (Integer) numsArr[0], max);
                System.out.println("max: " + max);
                if(stack.size() != 0){
                    p = stack.removeLast();
                    if(p.old == 0 && p.young == 0){
                        System.out.println("最大差值为： " + max); return;
                    }
                    p = stack.getLast();
                    nums.remove(nums.size() - 1);
                    System.out.println("移走元素后：" + nums.toString());
                    int pYoung = p.young;
                    if(map.get(p.young) != null && map.get(p.young).size() != 0){
                        p = new point(pYoung, map.get(pYoung).poll());
                    }
                    else {
                        p = null;
                    }
                }
            }

        }


    }
}

发表于 2020-03-28 00:52:03 回复(0)
kakifuu头像 kakifuu 
import java.util.*;

public class Main {

    static class Node {
        List<Node> children = new ArrayList<>();
        int val;

        Node(int val) {
            this.val = val;
        }

        void addChild(Node child) {
            this.children.add(child);
        }
    }

    private int res = Integer.MIN_VALUE;
    private int max;
    private int min;

    private void sln() {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 0; t < T; t++) {
            int n = scanner.nextInt();
            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                int val = scanner.nextInt();
                nodes[i] = new Node(val);
            }
            for (int i = 0; i < n - 1; i++) {
                int parentNo = scanner.nextInt(), childNo = scanner.nextInt();
                nodes[parentNo].addChild(nodes[childNo]);
            }
            min = nodes[0].val;
            max = nodes[0].val;
            dfs(nodes[0]);
            System.out.println(res);
        }
    }

    private void dfs(Node node) {
        if (node.children.isEmpty()) {
            res = Math.max(res, max - min);
        } else {
            for (Node child : node.children) {
                int oldMax = max, oldMin = min;
                max = Math.max(max, child.val);
                min = Math.min(min, child.val);
                dfs(child);
                max = oldMax;
                min = oldMin;
            }
        }
    }

    public static void main(String[] args) {
        new Main().sln();
    }
}

发表于 2019-12-06 14:32:42 回复(0)
下午约球不头像 下午约球不 
#include <iostream>
#include <algorithm>
#include<vector>
#include<string>
using namespace std;
struct Node{
	int data;
	vector<int> childs;
	Node(){
		data = -1;
	}
};
int n;
const int MAXSIZE = 100000;
Node tree[MAXSIZE];
vector<int>tmp_diff;
vector<int>tmp_stack;
int _max;
int _min;
void dfs(int idx){
	tmp_stack.push_back(idx);
	if (tree[idx].childs.size() == 0){
		_max = INT_MIN;
		_min = INT_MAX;
		for (int i = 0; i < tmp_stack.size(); i++){
			int index = tmp_stack[i];
			_max = max(_max, tree[index].data);
			_min = min(_min, tree[index].data);
		}
		tmp_diff.push_back(_max - _min);
	}
	else{
		for (int i = 0; i < tree[idx].childs.size(); i++){
			dfs(tree[idx].childs[i]);
		}
	}
	tmp_stack.pop_back();
}
int main() {
	cin >> n;
	int data;
	for (int i = 0; i < n; i++){
		cin >> data;
		tree[i].data = data;
	}
	int father, child;
	for (int i = 0; i < n - 1; i++){
		cin >> father >> child;
		tree[father].childs.push_back(child);
	}
	dfs(0);

	int _max = INT_MIN;
	for (int i = 0; i < tmp_diff.size(); i++){
		_max = max(_max, tmp_diff[i]);
	}
	cout << _max << endl;
	return 0;
}

发表于 2019-08-07 11:50:35 回复(1)
岚匀头像 岚匀 
#include<cstdio>
#include<algorithm>
#include<climits>
#include<map>
using namespace std;
const int MAXN = 100000;

struct Node{
    int data; // 节点有自己的下标 
    vector<int> childs; // 一个节点有自己的孩子 
    Node(){
        data = -1;
    }
};

Node tree[MAXN];

int n;// 节点之和 

vector<int> tmp_dif;
vector<int> tmp_seq;
int _max;
int _min;
void _tdfs(int idx){
    // 首先读根节点 
    tmp_seq.push_back(idx);
    if(tree[idx].childs.empty()){ // 当前节点是孩子节点 
        // 循环求出最大最小值
        int this_idx;
        _max = INT_MIN;
        _min = INT_MAX;
        for(int i = 0; i < tmp_seq.size(); i++){
            //printf("%d ", tmp_seq[i]);
            this_idx = tmp_seq[i];
            _max = max(_max, tree[this_idx].data);
            _min = min(_min, tree[this_idx].data);
        }
        //printf("\n");
        tmp_dif.push_back(_max - _min);
    } else{
        // 不是孩子节点就循环递归下去
        for(int i = 0; i < tree[idx].childs.size(); i++){
            _tdfs(tree[idx].childs[i]);
        } 
    }
    tmp_seq.pop_back();
}

int main(){
    // 处理输入 
    scanf("%d", &n);
    int data;
    for(int i = 0; i < n; i++){
        scanf("%d", &data);
        tree[i].data = data;
    }
    //构建树
    int father;
    int child;
    for(int i = 0; i < n - 1; i++){
        scanf("%d %d", &father, &child);
        tree[father].childs.push_back(child);
    }

    // 无论如何都要看所有的路径，那么直接深度优先搜索
    _tdfs(0); 

    // 取最大结果
    int _max = INT_MIN;
    for(int i = 0; i < tmp_dif.size(); i++){
        _max = max(_max, tmp_dif[i]); 
    } 
    printf("%d", _max);

    return 0;
}

/**
9
5 3 7 8 1 6 6 3 4
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8

正确答案:5 
*/
发表于 2019-08-05 20:55:00 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 虾皮信息 2019 Java工程师
来自：Shopee 2019...
上传者：小小
难度：
6条回答 6602浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号