5개의 댓글이 있습니다.
-
-
JongMan -
아시아 태평양 정보올림피아드라니.. 이런 대회가 있었나요? 첨 들어 보는 ㄷㄷㄷㄷ
어쨌건, 단체의 번호 목록이 주어졌을 때 그 중 최대 몇 개의 단체가 컨벤션 센터를 사용할 수 있는지 반환하는 함수 solve(vector) 가 있다고 합시다. 맨 처음, 1..n 의 모든 수를 채운 벡터를 넘겨주면 이것이 우리가 원하는 답이 되지요. 이 수를 S 라고 합시다.
모든 답들 중, 가장 사전순으로 앞에 있는 것은 1번 단체가 포함된 답입니다. 따라서, 1번 단체에게 컨벤션 센터를 빌려주고 남은 단체 중 S-1 개의 단체에게 컨벤션 센터를 빌려줄 수 있다면 항상 답에는 1번 단체가 포함되겠죠? 만약 1번 단체와, 1번과 겹치는 단체들을 모두 빼고 solve() 를 돌려봤더니, S-2 가 나왔다면? 1번 단체가 포함되는 답은 아무리 커봐야 S-1 이라는 것이겠죠?
이런 식으로 그리디하게 해나가면 됩니다. :)
15년 전 link
-
-
-
Taeyoon_Lee -
우선 끝나는 시간을 내림차순으로 정렬한 후에,
평범한 방법(?)으로 O(NlogN)만에 i번째 단체가 컨벤션 센터를 사용했을 때, 얻을 수 있는 최대 답을 구해놓고,
그 데이터를 토대로 사전순으로 가장 작은 답을 만들면 되지 않을까요'-'?
15년 전 link
-
-
-
Taeyoon_Lee -
해의 집합을 사전순으로 하는 것이군요...OTL
15년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
wisung
apio 2009 문제인데..
http://apio2009.iarcs.org.in/problems/apio2009-kr.pdf
여기서 문제 2번을 읽어보니 2번이 무척 어렵네요.
무슨 좋은 풀이 없을까요? 간단한 문제인 듯 한데도 사전순때문에 골치아프네요.. ;; ㄲㄲ
15년 전