nisroeld99   6달 전

Greedy로 푸는 문제일텐데


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


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


vector로 2중 loop 안되서


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


TLE에서 잡히네요 ㅠㅠ 


힌트좀 주세요


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

joonas   6달 전

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

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

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

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

nisroeld99   6달 전

ㄷㅏ뼌 감사합니다


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


어디가 틀ㄹ렸을까요 



nisroeld99   6달 전

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

joonas   6달 전

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

joonas   6달 전

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

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

nisroeld99   6달 전

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


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


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


아무튼 감사합니다 ㅋㅋ 



joonas   6달 전

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

10 100
50 90
60 80

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

ㅎㅎ화이팅하세요

nisroeld99   6달 전

10 100 50 90 60 80  입력시  

3

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

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