글 읽기 - 이분 탐색 중간 overflow 관련 질문.

amatuer789 5년 전 0

long long 타입으론 정답인데, int형으로 대체하니 '시간 초과'가 나서 질문드립니다.

하단 코드는 '시간초과' 나는 코드로, 25번줄을 수정하였습니다.

overflow 발생하지 않는 case와 똑같은 mid를 산출하는 것 같은데..

답변 부탁드리겠습니다~

#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
int k, n, ans, lo, hi, mid;
int L[10005];
bool is_n(int len){
    int i, cnt = 0;
    for(i = 1; i <= k; i++){
        cnt += (L[i]/len);
        if(cnt >= n) return true;
    }
    return false;
}
int main(){
    int i;
    scanf("%d%d", &k, &n);
    for(i = 1; i <= k; i++)
        scanf("%d", &L[i]);
        
    sort(&L[1], &L[k+1], greater<int>());
    lo = 1;
    hi = L[1];
    while(lo <= hi){
        mid = lo+(hi-lo)/2;
        if(is_n(mid)){
            ans = mid;
            lo = mid+1;
        }else{
            hi = mid-1;
        }
    }
    printf("%d", ans);
}

windflower 5년 전 2

hi low 둘 다 2^31-1인 경우 mid+1과정에서 오버플로우가 발생하지 않을까요

amatuer789 5년 전 0

그러네요 ... lo가 음수로 가버리겠군요 ...

감사합니다~

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

문제

문제

출처

ICPC

이분 탐색 중간 overflow 관련 질문.

amatuer789 5년 전 0

windflower 5년 전 2

amatuer789 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말