首页 > 试题广场 >

服务器数据分发

[编程题]服务器数据分发
  • 热度指数：634 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
【题干描述】：
我们共有n台服务器，每台服务器可以和若干个子服务器传输数据，n台服务器组成一个树状结构。
现在要将一份数据从root节点开始分发给所有服务器。
一次数据传输需要一个小时时间，
一个节点可以同时对k个儿子节点进行并行传输，
不同节点可以并行分发。
问，全部分发完成，最短需要多少小时？

【示例】：
当共有5台服务器，其树状结构为
       0
     /     \
   1      2
  /   \
 3    4
假设每一台服务器同时可以对1个儿子节点（k=1）并行传输，最优的数据传输过程示例如下：
    第一个小时，0 -> 1；
    第二个小时，1->3 & 0->2；
    第三个小时，1 -> 4;
所以当k=1时，全部分发完成最短需要3个小时。
假设每一台服务器同时可以对2个儿子节点（k=2）并行传输，最优的数据传输过程示例如下：
    第一个小时，0 -> 1 & 0 -> 2;
    第二个小时，1 -> 3 & 1 -> 4;
所以当k=2时，全部分发完成最短需要2个小时。

输入描述:
首行输入包含两个参数，分别表示每台服务器允许k个子节点并行传输，以及剩余输入行数。
其他行用于服务器树状结构描述，每一行表示一个父节点以及父节点对应的所有子节点。每一行都通过空格符分割不同数字，第一位数字为父节点及其所有子节点个数，第二位数字为父节点编号，其他数字为对应的子节点编号。


输出描述:
输出全部服务器分发完成，需要的最短时间。
示例1

输入

1 2
3 0 1 2
2 1 3

输出

2

备注:
1、服务器树状结构只有一个根节点，且根节点编号为0。

2、服务器个数n未知，但服务器编号取值范围为[0, n-1]。

3、n<=1000000
算法知识视频讲解
添加回答
石郎头像 石郎 

#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
#include <algorithm>
using  namespace std;

const  int MAX_V=1000005;
//用于存储树
vector<int> tree[MAX_V];
int cmp(int a,int b){
    return a>b;
}
int k;
int get_result(int root){
    // 如果当前节点没有孩子，即使叶子节点，那么它就不需要分发，直接返回0
    if (tree[root].empty()){
        return 0;
    }
    //用于存储每个孩子节点分发完的时间
    vector<int>tres;
    for (int v : tree[root]) {
        tres.push_back(get_result(v));
    }
    // 计算root节点的分发时间
    // root分发的时候，先发给，那些分发完所需时间最长的子节点
    sort(tres.begin(),tres.end(),cmp);
    int ares=0;
    for (int i = 0; i <tres.size() ; ++i) {
        tres[i]=tres[i]+floor(i*1.0/k)+1;
        ares=max(ares,tres[i]);
    }
    return ares;

}
int main(){
    int row_num,num,parent,child;
    //输入
    cin>>k>>row_num;
    for (int i = 0; i <row_num ; ++i) {
        cin>>num>>parent;
        for (int j = 0; j <num-1 ; ++j) {
            cin>>child;
            tree[parent].push_back(child);
        }
    }
    //计算根结点的最短分发时间
    cout<<get_result(0);
    return 0;
}


编辑于 2020-07-14 13:46:22 回复(2)
奶茶妹夫头像 奶茶妹夫 
import java.util.*;

/**
 * 	1. 使用hashmap构建树形结构
 * 	2. 递归分治法：假设已知 各个子节点的分发时间：
 *     	则： 2.1 对子节点的分发时间进行降序排列
 *     	    2.2 当前节点优先对 子节点分发时间 较长的节点进行分发, 
 * 				如:子节点分发时间 4 2 1 1 1 0, k=2, 则: 先后分发顺序(42)(11)(10),也就是
 *                     (42)+1 (11)+2 (10)+3 => 5 3 3 3 4 3 => 分三轮分发, 最终所需时间为 5 h。
 *             2.3 当节点为叶子结点, 分发时间为0
 *             2.4 最后使用分治法进行递归分发,相当于从叶子节点向上推。
 */
class Node{

    int id = 0;
    List<Node> sons = new ArrayList<>();
    Node parent = null;
}

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        HashMap<Integer , Node> hashMap = new HashMap<>();

        int K = sc.nextInt();
        int N = sc.nextInt();

        if(K == 0 || N == 0){
            System.out.println(0);
        }

        sc.nextLine();

        //树形构建
        for(int i = 0;i < N;i++){
            int node_n = sc.nextInt();
            //指定父节点
            int parent_id = sc.nextInt();
            Node my = null;
            if(hashMap.containsKey(parent_id)){
                //父节点存在
                my = hashMap.get(parent_id);
            }else{
                //父节点不存在
                my = new Node();
                my.id = parent_id;
                hashMap.put(parent_id,my);
            }
            //儿子节点
            for(int j = 0;j < node_n - 1;j++){
                int son_id = sc.nextInt();
                if(hashMap.containsKey(son_id)){
                    //儿子节点存在
                    hashMap.get(parent_id).sons.add(hashMap.get(son_id));
                }else{
                    //儿子节点不存在
                    Node son = new Node();
                    son.id = son_id;
                    son.parent = my;
                    hashMap.put(son.id,son);
                    hashMap.get(parent_id).sons.add(son);
                }
            }
            sc.nextLine();
        }

        //根节点存在
        Node root = hashMap.get(0);
        //分治法
        System.out.println(FZ(root , K));

    }

    public static int FZ(Node node , int k){
        int max = 0;
        if(node.sons.size() == 0){
            return 0;
        }else{
            Integer[] sons_time = new Integer[node.sons.size()];
            int i = 0;
            //统计分支时间
            for(Node son:node.sons){
                sons_time[i++] = FZ(son , k);
            }
            //合并分支与当前时间
            //降序排序
            Arrays.sort(sons_time, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
            //计算当前节点为root所需要的时间
            int add = 1;
            for(int j = 0; j < sons_time.length ; j++){
                if(j!=0 && (j%k) == 0){
                    add++;
                }
                sons_time[j] += add;
                if(sons_time[j] > max){
                    max = sons_time[j];
                }
            }
        }
        return max;
    }
}

发表于 2020-08-12 15:56:09 回复(3)
锐捷网络-招聘头像 锐捷网络-招聘 
#树结构
import sys
sys.setrecursionlimit(1000000)  # 解释器堆栈的最大深度
k,row_num=[int(v) for v in (sys.stdin.readline().strip('\n').strip().split())]
tree={}
root=0

for i in range(row_num):
    row = [int(v) for v in (sys.stdin.readline().strip('\n').strip().split())]
    if len(row)==0:
        continue
    if row[0]>1:
        tree[row[1]]=row[2:] #sorted(row[2:])

def get_result(root1):
    if len(tree.get(root1, [])) == 0:
        return 0
    tres=[]
    for v in tree.get(root1,[]):
        tres.append(get_result(v))
    tres=sorted(tres,reverse=True)
    for i in range(len(tres)):
        tres[i]=tres[i]+i//k+1
    return max(tres)

print(get_result(root))

发表于 2020-09-07 15:20:00 回复(0)
Shepherdeen头像 Shepherdeen
网络中信息传播的最短时间算法 - 百度学术 (baidu.com) 陈志斌 2003年。
发表于 2021-11-07 12:15:56 回复(0)
牛客632454464号头像 牛客632454464号
9、10两个案例***了，优化了好久才通过
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int k = in.nextInt(), N = in.nextInt();
        HashMap<Integer, treeNode> map = new HashMap<>();
        for(int i=0; i<N; ++i){
            int n = in.nextInt();
            if(n<1) continue;
            int key_root = in.nextInt();
            treeNode root = map.getOrDefault(key_root, new treeNode());
            while(n>1){
                --n;
                int key_child = in.nextInt();
                treeNode child = map.getOrDefault(key_child, new treeNode());
                root.add(child);
                child.parent = root;
                map.put(key_child, child);
            }
            map.put(key_root, root);
        }
        in.close();
        Main m = new Main();
        treeNode root = new treeNode();
        Queue<treeNode> queue = new LinkedList<>();
        for(treeNode node : map.values()){
            if(node.nums_child==0){
                m.getTime(k, node, queue);
            }
            if(node.parent==null){
                root = node;
            }
        }
        while(!queue.isEmpty()){
            m.getTime(k, queue.poll(), queue);
        }
        if(root.time>=0) System.out.println(root.time);
        else System.out.println(0);
    }
    public void getTime(int k, treeNode node, Queue<treeNode> queue){
        if(node.nums_child==0) {
            node.time = 0;
            if(node.parent!=null) {
                node.parent.nums_time++;
                if(node.parent.nums_time==node.parent.nums_child) queue.offer(node.parent);
            }
        }
        else if(node.nums_time==node.nums_child){
            Map<Integer, Integer> map = new HashMap<>();
            for(treeNode child : node.children){
                map.put(child.time, map.getOrDefault(child.time, 0)+1);
            }
            PriorityQueue<int[]> pqueue = new PriorityQueue<>(new Comparator<int[]>(){
                @Override
                public int compare(int[] o1, int[] o2){
                    return o2[0]-o1[0];
                }
            });
            for(int key : map.keySet()){
                pqueue.offer(new int[]{key, map.get(key)});
            }
            int used = 0, rest = 0;
            while(!pqueue.isEmpty()){
                int[] curr = pqueue.poll();
                if(rest<curr[1]) {
                    used += 1 + (curr[1]-rest-1)/k;
                    node.time = Math.max(curr[0] + used, node.time);
                    if((curr[1]-rest)%k!=0) rest = k-(curr[1]-rest)%k;
                    else rest=0;
                }
                else{
                    rest -= curr[1];
                }
            }
            if(node.parent!=null) {
                node.parent.nums_time++;
                if(node.parent.nums_time==node.parent.nums_child) queue.offer(node.parent);
            }
        }
    }
}
class treeNode {
    ArrayList<treeNode> children;
    int nums_child = 0;
    int nums_time = 0;
    int time = -1;
    treeNode parent;
    public treeNode(){
        children = new ArrayList<>();
    }
    public void add(treeNode node){
        children.add(node);
        nums_child++;
    }
}
发表于 2021-07-20 22:29:31 回复(0)
露西恩缇努维尔头像 露西恩缇努维尔
参考@石郎。真没想到用树形DP。 
#include<bits/stdc++.h>
using namespace std;

int dfs(unordered_map<int,vector<int>> &g,int root,int &k)
{
    if(!g.count(root))    return 0;
    vector<int> tree;
    for(auto &son:g[root])
    {
        tree.push_back(dfs(g,son,k));
    }
    sort(tree.begin(),tree.end(),greater<int>());
    
    int res=0;
    for(int i=0;i<tree.size();i++)
    {
        tree[i]+=floor(i*1.0/k)+1;
        res=max(res,tree[i]);
    }
    return res;
}

int main()
{
    int k,n;
    while(cin>>k>>n)
    {
        int root,cnt,son;
        unordered_map<int,vector<int>> g;
        for(int i=0;i<n;i++)
        {
            cin>>cnt>>root;
            for(int j=1;j<cnt;j++)
            {
                cin>>son;
                g[root].push_back(son);
            }
        }
        cout<<dfs(g,0,k)<<endl;
    }
    return 0;
}


发表于 2020-09-04 14:28:06 回复(0)
哈呀~😝头像 哈呀~😝
如果给出的测试用例内是按层次遍历顺序来排列的则有以下解法： 
var readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
var inputs = [];
rl.on('line', function(input) {
    inputs.push(input.trim());
    if(inputs[0].split(' ')[1] == inputs.length-1)
    {
        //每找到一个父节点，就让并可发次数加上本身一次
        //计算每行除了父节点的总个数，也就是求除了第一行的inputs的首个元素-1的总和-1
        //然后用总数减去每次找到后的并发数，共计减几次即为几小时
        var pNodeSum = inputs.length-2;
        var nodeSum = 0;
        var hour = inputs[0].split(' ')[0]-0;//-0是快速转化为数字
        var count = 0;
        for(let i = 1;i<inputs.length-1;i++)
            nodeSum+=inputs[i].split(' ')[0]-1;
        for(let j = pNodeSum;j>0;j--)
        {
            nodeSum -= hour;
            hour += hour;
            count++;
        }
        if(nodeSum>0)
            count+=Math.ceil(nodeSum/hour);
        console.log(count);
    }
})


发表于 2020-08-28 18:41:34 回复(0)
提交观点

问题信息

C++工程师 搜狗 前端工程师 算法工程师 测试工程师 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
7条回答 3733浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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