美团秋招笔试第四场

第二题 种树 AC

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int n,k;
    static int[] nums;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
//        n=in.nextInt();
//        k=in.nextInt();
//        nums=new int[n];
//        for(int i=0;i<n;i++)
//            nums[i]=in.nextInt();
        n=3;k=6;nums=new int[]{1,2,5};
        Arrays.sort(nums);
        for(int i=0;i<n-1;i++){
            nums[i]=nums[i+1]-nums[i];
        }
        nums[n-1]=Integer.MAX_VALUE;
        //要找到一个最小值 可以用二分查找 最大是k 最小是1
        int left=1,right=k,ans=k;
        while(left<=right){
            int mid=(left+right)>>1;
            if(canDo(mid)){
                ans=Math.min(ans,mid);
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        System.out.println(ans);
    }
    private static boolean canDo(int cur){
        //直接通过计算来判断能否成功
        Long sum=0L;
        for(int i:nums){
            sum+=Math.min(cur,i);
        }
        return sum>=k;
    }
}

第三题 通过了测试用例，提交不通过

刚刚又本地改了、测了一下，现在我觉得没问题了（？）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static int getDist(int l,int r,List<Integer> index){
        int dist=Integer.MAX_VALUE;
        for(int i:index){
            if(i<l)
                dist=Math.min(dist,l-i);
            else if(i>r)
            {
                dist=Math.min(dist,i-r);
                break;
            }
        }
        return dist+r-l+1;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
//        int n=in.nextInt();
//        int q=in.nextInt();
//        long[] nums=new long[n];
//        long max=0;
//        for(int i=0;i<n;i++){
//            nums[i]=in.nextLong();
//            if(nums[i]>max){
//                max=nums[i];
//            }
//        }
        int n=7,q=2;
        long max=5;
        long[] nums=new long[]{1,1,4,5,1,4,5,5};
        List<Integer> index=new ArrayList();
        for(int i=0;i<n;i++){
            if(nums[i]==max)
                index.add(i);
        }
        for(int i=0;i<q;i++){
            int l=in.nextInt()-1;
            int r=in.nextInt()-1;
            //1.判断输赢。也就是判断最大值在不在l到r 2.求区间长度应该是多少
            //列出所有情况。1必赢2平局3输了
            int flag=0,qujian=n;
            for(int idx:index){
                if(idx>=l&&idx<=r)//说明小团找到了一个最大值
                {
                    if(flag==1){//说明前面已经找到了一个落在这个区间的数字
                        flag=3;break;
                    }
                    if(index.size()>1)
                        flag=1;//如果不止一个最大值，那么可以平局
                    else {
                        flag = 2;
                        break;
                    }
                }else if(idx>=r)
                    break;
            }
            //针对三种情况，分别求区间长度
            if(flag==2){
                System.out.println("lose");
                //对方已经赢了 只需要加一
                qujian=r-l+2;
            }else if(flag==0){
                System.out.println("win");
                //只需要找到和这个区间最近的index
                qujian=getDist(l,r,index);
            }else{
                System.out.println("draw");
                //为了平局，同样要找到最近的index
                if(flag==3)
                    qujian=r-l+1;
                else
                    qujian=getDist(l,r,index);
            }
            System.out.println(qujian);
        }

    }
}