글 읽기 - TLE안나는법이 뭘까요

nisroeld99 7년 전 0

Greedy로 푸는 문제일텐데

어떻게하면시간초과가 안날까요?

아무리해도 O(nlongn + nm )을 못벗어나겠네요 (n 사람수 , m 기계수)

vector로 2중 loop 안되서

priority _queue 도 만들어보고 별 쑈를 다해봤는데

TLE에서 잡히네요 ㅠㅠ

힌트좀 주세요

코드는 저만 알아볼수있을거같아서 안올립니다

joonas 7년 전 1

nlogn 은 정렬 말하시는거같고, nm 을 priority_queue 쓰시면 줄일 수 있습니다.

저는 pq를 2개 썼는데, 하나는 사용중인 자리들 중에서 현재 사용하려는 사람(의 시작시간)보다 종료시간이 빠른 녀석들을 다 없애고 자리에 앉았습니다.

자리는 번호가 빠른 순으로 선택했구요.

근데 풀고나서 보니 더 좋은 방법이 있더군요 (.....

nisroeld99 7년 전 0

ㄷㅏ뼌 감사합니다

비슷하게 짠거같은데 틀리다고 뜨네요 ㅠㅠ

어디가 틀ㄹ렸을까요

#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;


bool comp(const ii & a , const ii & b){
    if (a.first== b.first ){
        return a.first < b.first ;
    }
    return a.first < b.first;
}
int main(){
    int n;
    scanf("%d",&n);
    vector<ii>v;
    
    while (n--){
        int s,e;
        scanf("%d%d",&s,&e);
        v.push_back(ii(s,e));
    }
    sort(v.begin(),v.end(), comp);
    
    priority_queue<ii,vector<ii>, greater<ii>> working;
    priority_queue<int,vector<int>, greater<int> > avail;
    
    int dab[111111];
    int cnt = 0;
    for (int i = 0 ; i< v.size() ; i++){
        while (!working.empty()) {
            if (working.top().first <= v[i].first){
                int computer=working.top().second ;working.pop();
                avail.push(computer);
            }
            else {
                break;
            }
        }
        if (avail.empty()){ //비어있으면 추가해줘라
            cnt++;
            dab[cnt]++;
            working.push(ii( v[i].second , cnt ));
            
        }
        else {  // 놀고있으면
            int now = avail.top() ; avail.pop();
            working.push(ii( v[i].second ,now ));
            dab[now]++;
        }
    }
    printf("%d\n",cnt);
    for (int i =1 ;i<=cnt;i++){
        printf("%d ",dab[i]);
    }
    
    
    
    printf("\n");
    
}

nisroeld99 7년 전 0

ㅎㅎㅎㅎ이거떄매 지금 하.. 오기나서 계속하는데 화나네요 막

joonas 7년 전 0

comp 함수에서 a.first < b.first 가 아니라 a.second 아니에요?

joonas 7년 전 1

그리고 if (working.top().first <= v[i].first) 는 앉아 있는 사람의 시작 시간과 현재 사용하려는 사람의 시작시간을 서로 비교하는 거 아닌가요?

if (working.top().second <= v[i].first) 로 바꾸는게 맞아보이네요.

nisroeld99 7년 전 1

vector <ii> working 안에는 < 종료시간 , 컴퓨터 번호 >

이렇게 입력되어있어서 종료시간 <= 현재 이용자 시작시간 비교는 맞는것 같습니다.

머리식히고 생각안날때쯤에 다시풀면 맞을것같습니다

아무튼 감사합니다 ㅋㅋ

joonas 7년 전 0

종료시간순으로 정렬하시면

10 100
50 90
60 80

에서 문제가 생길거같습니다.

ㅎㅎ화이팅하세요

nisroeld99 7년 전 0

10 100 50 90 60 80 입력시

1 1 1 아닌가요? 잘나오는거같아요 ㅠㅠ

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

문제

문제

출처

ICPC

TLE안나는법이 뭘까요

nisroeld99 7년 전 0

joonas 7년 전 1

nisroeld99 7년 전 0

nisroeld99 7년 전 0

joonas 7년 전 0

joonas 7년 전 1

nisroeld99 7년 전 1

joonas 7년 전 0

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말