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

vice_versa 3년 전 1

안녕하세요

문제를 풀다 궁금한 점이 생겨 글을 쓰게 되었습니다

두 번째 코드처럼 bs함수의 high의 초기값을 m과 t의 최대값의 곱인 10^18로 주면 틀리고

첫 번째 코드처럼 입력받은 수 중 최대t값 * m으로 주면 ac를 받습니다

high의 초기값을 10^18로 주는 코드로는 왜 통과할 수 없는지 여쭙고 싶습니다

//맞은 코드
//high의 초기값을 가장 오래걸리는 시간 * 친구의 수로 계산
#include <iostream>
#include <algorithm>
using namespace std;
unsigned long long n, m, ans = -1;
unsigned long long arr[100000];
void bs(unsigned long long low, unsigned long long high) {
	unsigned long long t = (low + high) / 2;
	unsigned long long temp = 0;
	for (int i = 0; i < n; i++) temp +=  t/ arr[i];
	if ((ans == -1 || t <= ans) && temp >= m) ans = t;
	if (low >= high) return;
	else if (temp >= m) bs(low, t - 1);
	else if (temp < m) bs(t + 1, high);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> arr[i];
	bs(1, (*max_element(arr,arr+n)) * m);
	cout << ans;
}



//틀린 코드
//high의 초기값을 t와 m의 최대값의 곱인 10^9 * 10^9로 계산
#include <iostream>
using namespace std;
unsigned long long n, m, ans = -1;
unsigned long long arr[100000];
void bs(unsigned long long low, unsigned long long high) {
	unsigned long long t = (low + high) / 2;
	unsigned long long temp = 0;
	for (int i = 0; i < n; i++) temp +=  t/ arr[i];
	if ((ans == -1 || t <= ans) && temp >= m) ans = t;
	if (low >= high) return;
	else if (temp >= m) bs(low, t - 1);
	else if (temp < m) bs(t + 1, high);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> arr[i];
	bs(0, 1000000000000000000);
	cout << ans;
}

pmn0001 3년 전 1

unsigned long long t = (low + high) / 2;

에서 high가 ull 최대 범위이면 low와 더했을때 오버플로우 발생할거 같아요

vice_versa 3년 전 0

그렇군요 감사합니다!

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

문제

문제

출처

ICPC

이분탐색 범위질문

vice_versa 3년 전 1

pmn0001 3년 전 1

vice_versa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말