글 읽기 - 시간초과.. 뭐가문제일까요..

malmang 5년 전 0

이분탐색으로 한건데 왜 시간초과가 날까요?? ㅜ

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    vector<int> tree;
    int sum=0;
    int min,mid,max,result,n,m,h;
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>h;
        tree.push_back(h);
    }
    sort(tree.begin(),tree.end());
    max = tree.back();
    min =0;
    while(min<=max){
        sum =0;
        mid =(max+min)/2;
        for(int i=0; i<tree.size(); i++){
            int block = tree[i]-mid>0? tree[i]-mid : 0;
            sum = sum + block;
        }
        if(sum>m){
            min =mid;
            result=mid;
        }
        if(sum<m){
            max=mid;
            result=mid;
        }
        if(sum==m){
            result=mid;
            break;
        }
    }
    cout<<result;
}

djm03178 5년 전 2

이분 탐색에서, 어떤 원소의 존재성만을 가리면 되는 것이 아니라면 기본적으로 lo와 hi가 만날 때까지 계속해야 합니다.

이 문제의 경우 sum이 m이 되는 경우가 아예 없을 수도 있습니다. 그래서 sum >= m인 최소의 지점을 구해야 합니다.

3 1
1 2 2

kyo20111 5년 전 1

min = 1 , max=2 일때를 생각해봅시다.

mid=(min+max)/2 = 1 가 나오고

sum의 결과가 m보다 작으면 min = mid = 1

다시 min=1 , max=2 인 상태로

아무런 변화 없이 계속 while문을 돌겁니다.

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

문제

문제

출처

ICPC

시간초과.. 뭐가문제일까요..

malmang 5년 전 0

djm03178 5년 전 2

kyo20111 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말