华为OD真题--快速开租建站-简单易懂写法

雨点打透心脏的1/2处 2023-10-13 10:18 33阅读 0赞

/\*\*  
\* 题目描述  
\* 当前 IT 部门支撑了子公司颗粒化业务，该部门需要实现为子公司快速开租建站的能力，建站是指在一个全新的环境部署一套 IT 服务。  
\* 每个站点开站会由一系列部署任务项构成，每个任务项部署完成时间都是固定和相等的，设为 1。  
\* 部署任务项之间可能存在依赖，假如任务 2 依赖任务 1，那么等任务 1 部署完，任务 2 才能部署。任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。  
\* 没有依赖的任务可以并行部署，优秀的员工们会做到完全并行无等待的部署。给定一个站点部署任务项和它们之间的依赖关系，请给出一个站点的最短开站时间。  
\*  
\* 输入描述  
\* 第一行是任务数 taskNum，第二行是任务的依赖关系数 relationsNum  
\*  
\* 接下来 relationsNum 行，每行包含两个 id，描述一个依赖关系，格式为：IDi IDj，表示部署任务 i 部署完成了，  
\* 部署任务 j 才能部署，IDi 和 IDj 值的范围为：\[0, taskNum)  
\*  
\* 注：输入保证部署任务之间的依赖不会存在环。  
\*  
\* 输出描述  
\* 一个整数，表示一个站点的最短开站时间。  
输入  
5  
5  
0 4  
1 2  
1 3  
2 3  
2 4  
  
  
  
0 0 0 0 1  
0 0 1 1 0  
0 0 0 1 1  
0 0 0 0 0  
0 0 0 0 0  
  
0 0 0 0 0  
0 1 0 0 0  
0 1 0 0 0  
0 0 1 0 0  
1 0 1 0 0  
  
  
0 3  
0 4  
1 3  
  
0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
1 1 0 0 0  
1 0 0 0 0  
  
0 0 0 1 1  
0 0 0 1 0  
0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
输出  
3  
说明  
有 5 个部署任务项，5 个依赖关系，如下图所示。我们可以先同时部署任务项 0 和任务项 1，然后部署任务项 2，最后同时部署任务项 3 和任务项 4。最短开站时间为 3  
\*/

public class SetSiteA {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int taskNum = Integer.parseInt(sc.nextLine());
            int [][] step = new int[taskNum][taskNum];
            int relyNum = Integer.parseInt(sc.nextLine());
            int stepCount = 1;
            List<Integer> comp = new ArrayList<>();
            for (int c = 0; c < taskNum; c++){
                comp.add(c);
            }
    
            for(int i = 0; i < relyNum;i++){
                String [] value = sc.nextLine().toString().split(" ");
                int x = Integer.parseInt(value[0]);
                Integer y = Integer.parseInt(value[1]);
                //构建任务数的矩阵，存在依赖关系的值为1
                step[x][y] = 1;
                comp.remove(y);
            }
            //重复遍历，直到所有任务完成
            while (comp.size() != taskNum){
                //依赖已完成的任务全部刷成0
                Set<Integer> set = new HashSet<>();
                for (int k = 0; k < comp.size();k++){
                    for(int j = 0; j < taskNum;j++){
                        //减枝，减少遍历次数
                        if (step[k][j] == 1){
                            set.add(j);
                        }
                        step[k][j] = 0;
                    }
                }
                //检查是不是有任务已全部完成,根据Y列，已完成的加入已完成的compList中
                for(Integer value : set){
                    boolean b = true;
                    for(int j = 0; j < taskNum;j++){
                        if (step[j][value] != 0){
                            b = false;
                            break;
                        }
                    }
                    if (b){
                        comp.add(value);
                    }
                }
                stepCount++;
            }
            System.out.println(stepCount);
        }
    
    }