글 읽기 - 이분탐색 최대값 질문입니다.

joseph415 5년 전 0

long long h = n[a-1]*b;

라고 상한선을 잡으니 꼐속 틀렸습니다. 라고 뜨더라고요 이유를 모르겠습니다.

커버 된다고 생각했는데 안되는 경우가 대체 뭔지 모르겠습니다ㅠㅠㅠ 도와주세요

상한선을 10억*10만 으로 잡으니 풀렸는데 왜 저처럼하면 틀린건가요

#include <iostream>
#include <algorithm>
using namespace std;
long long cnt=0;
void search(long long n[],int a,long long b) {
    long long h = n[a-1]*b;   // b는 인원수 n[a-1]는 가장오래걸리는 심사대
    long long l = 0;
    long long max=h;
    long long mid = (h + l) / 2;
    while (h>=l) {
        for (int i = 0; i < a; i++) {
            cnt+=mid/n[i];
        }
        if (cnt>=b) {
            if(mid<max)
                max = mid;
            h = mid - 1;
            mid = (l + h) / 2;
        }
        if(cnt<b){
            l=mid+1;
            mid=(l+h)/2;
        }
        cnt=0;
    }
    cout<<max;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a;
    long long b;
    cin>>a>>b;
    long long n[100001]={};
    for(int i=0;i<a;i++)
        cin>>n[i];
    sort(n,n+a);
    search(n,a,b);
}

chogahui05 5년 전 0

흑흑.. 고생했쟈나요. ㅋㅋ

채점번호 11612419, 11612363, 11612211를 조회해 본 결과

아래와 같은 테스트 케이스에서 반례를 뿜는 것을 발견했습니다.

chogahui05 5년 전 0

참고로 저 케이스의 답은 24입니다.

상근 친구 1,2,3이 게이트 1

상근 친구 4,5,6이 게이트 2

이렇게 통과하면 24초가 걸리겠져. 실제로 diffchecker라는 사이트에서 코드 대조해 본 결과

15번째 줄에 걸리는 if문이 조건이 다르다는 것을 확인하였는데 이 부분의 차이 때문에 특정한 케이스에서 다르게 답이 나온 것으로 보여요.

이는 상한선과 관계는 없어보이고, 이분 탐색을 할 때 if 조건을 잘못 걸어서 그런게 아닌가 싶습니다.

상한선은 말씀대로 b*n[a-1]까지 주는 게 맞아보입니다. 어짜피 그 이상 줘 버리면 당연하게도 모두 통과 가능한 게 맞으니까요.

담부턴 잘 되는 코드 확인하고 올려주셨으면 좋겠다는 것이에요.

물론 이 코드 반례 찾아달라. 테케 약한 거 같다.. 그럼 어떻게던 노가다를 해 보긴 하겠다만요.

2 6
8
8

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

문제

문제

출처

ICPC

이분탐색 최대값 질문입니다.

joseph415 5년 전 0

chogahui05 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말