글 읽기 - 3020번 이분탐색으로 했는데 어디가 틀렸는지 모르겠습니다

dkwlsfk22 3년 전 0

구간을 통과하는 종유석, 석순의 개수를 구하기 위해 통하지 않는 최대 길이를 이분탐색으로 구하여 upper_bound로 구해줬습니다.

테케는 맞다고 나왔는데 어디서 틀렸는지 알 수 있을까요ㅠㅠ? 도와주세요..

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

public class B3022 {
    private static int upperBound(int[] arr, int target) {
        int begin = 0;
        int end = arr.length;
        
        while(begin < end) {
            int mid = (begin + end) / 2;
            
            if(arr[mid] <= target) {
                begin = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return end;
    }

    public static int cnt(int[] arr , int aim) {
        int cnt = 0;
        int left = 0; int right = arr.length;
        int upperbound = -1;
        int mid = 0;
        while(left < right) {
            mid = (left+right)/2;       
            if(arr[mid] == aim) {
                upperbound = upperBound(arr, arr[mid]);
                break;
            }
            if(arr[mid] < aim) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        if(upperbound == -1 ) upperbound = upperBound(arr, 0); 
        // System.out.println("aim : "+aim+" , upperbound : "+upperbound);
        cnt += (arr.length - upperbound);
        return cnt;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]); 
        int H = Integer.parseInt(inputs[1]); 
        int[] counts = new int[H+1];
        int[] up = new int[500001];
        int[] down = new int[500001];
        for(int i=0 ; i<n ; i++) {
            if(i%2 == 0 ) {
                down[i] = Integer.parseInt(br.readLine());
            }else{
                up[i] = Integer.parseInt(br.readLine());
            }
        }
        Arrays.sort(up);Arrays.sort(down);
        for(int h = 1; h<= H ; h++ ){
            //up : 구간이 3일때 h-1의 upperbound를 찾아야함
            counts[h] = cnt(up, H-h);
            //down : 구간이 3일때 H-h의 upperbound 찾음            
            counts[h] += cnt(down, h-1);
        }
        Arrays.sort(counts);       
        System.out.println(counts[1]+" " + (upperBound(counts, counts[1])-1));
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3020번 이분탐색으로 했는데 어디가 틀렸는지 모르겠습니다

dkwlsfk22 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말