글 읽기 - c++ 시간초과 질문이요...

ch37ch37 4년 전 0

7%까지 가다가 시간초과가 계속 뜹니다 ㅠㅠ

다른질문보니까 multiset을 쓰라고 하시는데 어떤 방식으로 쓰면될까요?

혹시 안쓰고 푸는 방법은 없나요?

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>

using namespace std;

bool compare(pair<int,int> a,pair<int,int> b){
    if(a.first == b.first){
        return a.second > b.second;
    }else{
        return a.first  < b.first;
    }
}

int main(void){

    int N,K,sum=0;
    cin >> N >> K;
    pair<int,int> p[N];
    int bag[K];
    for(int i=0;i<N;i++){
        cin >> p[i].first >> p[i].second;
    }
    for(int i=0;i<K;i++){
        cin >> bag[i];
    }

    sort(p,p+N,compare);
    sort(bag,bag+K);

    for(int i=0;i<K;i++){
        int index=-1,j=0,MAX = 0;
        while(bag[i] >= p[j].first && j<N){
            if(p[j].second >= MAX){
                MAX = p[j].second;
                index = j;
            }
            j++;
        }
        sum = sum + MAX;
        if(index != -1){
            p[index].second=0;
        }
    }

    cout << sum;

    return 0;

}

wjsqjawns 4년 전 0

N과 K의 범위가 최대 30만이며, 올려주신 코드의 반복문의 시간복잡도가 O(NK)이기에 시간초과가 발생합니다.

단순하게 생각해서, 비싼 보석일수록 우선도가 높으며, 이를 넣을 수 있는 가방이 존재하는지를 확인하기만 하면 되기에,

multiset의 lower_bound() 함수( O(log K) )를 이용하시면 편할 거에요.

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

문제

문제

출처

ICPC

c++ 시간초과 질문이요...

ch37ch37 4년 전 0

wjsqjawns 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말