문제

풀이

1. 석순과 종유석 up down 배열로 나눠서 저장
2. 석순 종유석 정렬
3. 이분탐색 lower bound로 개수를 구해준다.

   ---

코드

import java.io.*;
import java.util.*;

public class Main {

    static int n,h;

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        h=Integer.parseInt(st.nextToken());
        int[] up=new int[n/2];
        int[] down=new int[n/2];
        for(int i=0;i<n;i++){
            if(i%2==0){
                up[i/2]=Integer.parseInt(br.readLine());
            }
            else down[i/2]=Integer.parseInt(br.readLine());
        }

        Arrays.sort(up);
        Arrays.sort(down);

        int min=200001;
        int ans=0;
        for(int i=1;i<=h;i++){
            int cnt=0;
            cnt+=bs(up,i);
            cnt+=bs(down,h-i+1);
            if(min>cnt){
                min=cnt;
                ans=1;
            } else if (min==cnt) {
                ans++;
            }
        }

        System.out.println(min+" "+ans);
    }

    static int bs(int[] arr,int height){
        int l=0;
        int r=n/2;
        int mid=0;
        while(l<r){
            mid=(l+r)>>1;
            if(height<=arr[mid])r=mid;
            else l=mid+1;
        }
        return n/2-r;
    }

}

#이분탐색