华为机试8.25第三题_

题目大意:给你一系列任务的完成时间及其前置依赖,任务可以并行,求完成所有任务的最短时间 

输入: 
第一行一个数n代表有n个任务,接下来n行代表每个任务的信息 
当没有前置依赖的时候,这一行为-1 t,t代表完成时间 
当有前置依赖的时候,前置依赖间用逗号隔开,1,2 t,t代表完成时间 
Java split处理字符串yyds 
拓扑排序加dp,其中dp[i]代表完成第i个任务需要的时间
dp[i]=(dp[j])+time[i]dp[i]=(j,i)Emax?(dp[j])+time[i]
作者:相依相随
链接:https://www.nowcoder.com/discuss/719729?type=post&order=time&pos=&page=3&ncTraceId=&channel=-1&source_id=search_post_nctrack
来源:牛客网

package nowcoder;
 
import java.io.BufferedInputStream;
import java.util.*;
 
public class Main49 {
    public static void main(String[] args) {
        new Solve49().solve();
    }
}
 
class Solve49{
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        int n=s.nextInt();
        int[] times=new int[n];
        s.nextLine();
        List<List<Integer>> graph=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            String str=s.nextLine();
            String[] strs=str.split(",");
            for (int j = 0; j <strs.length-1 ; j++) {
                int a=Integer.parseInt(strs[j]);
                graph.get(a).add(i);
            }
            String[] curr=strs[strs.length-1].split(" ");
            if (!curr[0].equals("-1")){
                int a=Integer.parseInt(curr[0]);
                graph.get(a).add(i);
            }
            int t=Integer.parseInt(curr[1]);
            times[i]=t;
        }
        System.out.println(getAns(times,graph,n));
    }
    private int getAns(int[] times,List<List<Integer>> graph,int n){
        int[] in=new int[n];
        for(List<Integer> list:graph){
            for(int i:list)in[i]++;
        }
        Queue<Integer> queue=new LinkedList<>();
        int[] dp=new int[n];
        Arrays.fill(dp,0);
        int cnt=0;
        for (int i = 0; i < n; i++) {
            if (in[i]==0){
                dp[i]=times[i];
                queue.add(i);
            }
        }
        while (!queue.isEmpty()){
            int curr=queue.poll();
            cnt++;
            for(int i:graph.get(curr)){
                in[i]--;
                dp[i]=Math.max(dp[i],dp[curr]+times[i]);
                if (in[i]==0)queue.add(i);
            }
        }
        if (cnt!=n)return -1;
        int ans=0;
        for (int i = 0; i <dp.length ; i++) {
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
 
}

 

 

华为机试8.25第三题_

上一篇:功能测试理论基础知识


下一篇:lpad()和Rpad()函数的用法