글 읽기 - 시간초과를

johyesong8686 3년 전 0

1.우선 보석의 가치가 높은 거를 우선 순위로 배열 했습니다.

2.for 문을 통해서 이분탐색 o(logn)을 사용하여 무게가 동일 하거나 큰 것을 찾아서

ans 에 값을 더해준 뒤 erase 하여 사용한 가방을 삭제하는 방식으로 구현 했습니다.

1. 시간 초과 원인은 어디서 나오는건가요 ? 이분 탐색인가요 ?

2.이 문제를 해결하기 위해서 이 논리에서 추가해야할 부분이 있나요 ? 아니면 아예 논리를 바꿔서 풀어야할까요 ?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<long long> bag;
vector<pair<long long, long long> > p;
int binary_search(long long num)
{
    int lo = 0;
    int hi = bag.size() - 1;
    int temp = -1;
   // cout <<num <<'\n';
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        int cur = bag[mid];
       //  cout <<cur <<'\n';
        if (cur >=num)
        {    hi=mid-1;
             if (temp < mid){
                 temp = mid;
               
            }
             
        }
        else
        {
           lo = mid + 1;
            
        }
    }

    return temp;
}
bool cmp(pair<long long, long long> &a, pair<long long, long long> &b)
{
    if (a.second == b.second)
    {
        return a.first > b.first;
    }
    else
    {
        return a.second > b.second;
    }
}
int main(void)
{

    int n, k;
    cin >> n >> k;
    
  
    for (int i = 0; i < n; i++)
    {
        long long x, y;
        cin >> x >> y;
        p.push_back(make_pair(x, y));
    }
    for (int j = 0; j < k; j++)
    {
        long long x;
        cin >> x;
        bag.push_back(x);
    }
   
    sort(p.begin(), p.end(), cmp);
    sort(bag.begin(), bag.end());
   long long ans=0;
   
    for(int i=0; i<n;i++){
        int index;
        if(bag.size()==0){
            break;
        }
        index=binary_search(p[i].first);
         ans+=p[i].second;
         bag.erase(bag.begin()+index);
         
    }
    cout <<ans <<'\n';
    
    

    return 0;
}

johyesong8686 3년 전 0

bag.erase() 의 시간 복잡도가 o(n)을 지니고 있기때문입니다.

for문에 들어갈경우 시간 초과가 나겠죵

kcan1416 3년 전 1

erase가 문제입니다

이대로 푸시려면 vector대신 multiset로 바꿔서 하심 되고
우선순위큐로도 할 수 있는데 대신 푸는 방식이 바뀝니다

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

문제

문제

출처

ICPC

시간초과를

johyesong8686 3년 전 0

johyesong8686 3년 전 0

kcan1416 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말