글 읽기 - 이분탐색 범위 관련 질문

yeohj0710 1년 전 2

https://www.acmicpc.net/board/...

위와 동일한 질문인데, 마땅한 답변이 없어 질문 남깁니다.

(답변에서 오버플로우가 발생한다고 하였는데 탐색 범위의 최댓값은 1e18이고 ull의 범위는 최대 1.8e19이므로 질문자님의 코드에서는 오버플로우가 발생하지 않는 것으로 보입니다. 아니면 혹시 제가 잘못 생각하고 있는 걸까요?)

혹시 아래 코드에 반례가 존재할까요?

(참고로 아래 코드는 WA 처리를 받고 sort(v.begin(), v.end()); 해준 뒤 r = ans = M * v[N-1]; 으로 잡아야 AC를 받습니다.)

감사합니다.

+ 아 참고로 #define 때문에 int가 long long으로 사용되고 있습니다. int를 long long으로 봐주시면 됩니다.

#include <bits/stdc++.h>
#define int long long
using namespace std;

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    int l = 0, r = 1e18, ans = 1e18;

    while(l <= r) {
        int m = (l + r)/2;

        int sum = 0;
        for(int i=0; i<N; i++) sum += m / v[i];

        if(sum >= M) {
            ans = min(ans, m);
            r = m - 1;
        }
        else l = m + 1;
    }

    cout << ans << "\n";
}

sete3683 1년 전 1

바로 아랫글의 데이터가 반례가 될 것 같습니다

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

문제

문제

출처

ICPC

이분탐색 범위 관련 질문

yeohj0710 1년 전 2

sete3683 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말