题解 | 牛客周赛 Round 85 EF Java题解

EF Java题解，代码已去除冗余~~~

E 小紫的线段染色

可先按照线段末尾升序排列，并记载两个涂色的最末端位置，依次将线段优先放到末端最靠后的颜色（否则尝试放到末端靠前的颜色），如果遇到无法放入，则直接返回-1；最后需要注意的是，涂成紫色的线段至少要有一条，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),seg[][]=new int[n][],l1=-1,l2=-1;
        for(int i=0;i<n;i++){
            seg[i]=new int[]{sc.nextInt(),sc.nextInt(),i+1};
        }
        Arrays.sort(seg,(a,b)->Integer.compare(a[1],b[1]));
        List<Integer> ans=new ArrayList<>();
        for(int p[]:seg){
            if(l1>=l2){
                if(p[0]>l1){
                    l1=p[1];
                    ans.add(p[2]);
                }
                else if(p[0]>l2){
                    l2=p[1];
                }
                else{
                    System.out.println("-1");
                    return;
                }
            }
            else{
                if(p[0]>l2){
                    l2=p[1];
                }
                else if(p[0]>l1){
                    l1=p[1];
                    ans.add(p[2]);
                }
                else{
                    System.out.println("-1");
                    return;
                }
            }
        }
        if(ans.size()==0){
            ans.add(1);
        }
        System.out.println(ans.size());
        for(int a:ans){
            System.out.print(a+" ");
        }
    }
}

F 小紫的树上染色

可二分答案，对于指定的连通块最大值，依次对图进行深搜，并记录当前子树的连通块大小，若超过最大值，则需要将此节点涂色，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt(),l=0,r=n;
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        while(l<r){
            int mid=(l+r)>>1;
            if(find(1,0,mid,path)[1]<=k){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        System.out.println(r);
    }
    static int[] find(int k,int p,int max,List<Integer> path[]){
        int ans[]=new int[]{1,0};
        for(int a:path[k]){
            if(a!=p){
                int cur[]=find(a,k,max,path);
                ans[1]+=cur[1];
                ans[0]+=cur[0];
            }
        }
        if(ans[0]>max){
            ans[1]++;
            ans[0]=0;
        }
        return ans;
    }
}