글 읽기 - 이분탐색 질문

djgjdgjd 6년 전 0

아래 코드에서 이분탐색 시 전역변수 s를 0이 아닌 1로 하면 제대로 이분탐색이 안되는 이유가 뭔가요??

#include <cstdio>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

int n, m, k;
vector<long long> v;
long long maxV = 0, sum = 0;
long long s = 0;    //    1로 하면 안되는 이유
long long e = 9223372036854775807;

long long solve(long long start, long long end)
{
    while(start <= end)
    {
        long long mid = (start + end) / 2;
        int ret = 0;
        
        for(int i=0;i<k;i++)
            ret += v[i] / mid;
        
        if(ret >= n)
        {
            start = mid+1;
            
            if(mid > maxV)
                maxV = mid;
        }
        else
            end = mid - 1;
    }
    
    return maxV;
}

int main()
{
    long long num;
    cin>>k>>n;

    for(int i=0;i<k;i++)
    {
        cin>>num;
        v.push_back(num);
    }
    
    sort(v.begin(), v.end());
    
    cout<<solve(s, e)<<'\n';
    
    return 0;
}

jh05013 6년 전 1

오버플로우로 인해 맨 처음의 mid 값이 제대로 계산되지 않습니다.

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

문제

문제

출처

ICPC

이분탐색 질문

djgjdgjd 6년 전 0

jh05013 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말