ABC124-D : Cake 123

Cake 123 (Need to Review!)

https://atcoder.jp/contests/abc123/tasks/abc123_d

  • 처음에 읽었을때는 해답을 못찾고 벙쪄 있었다. 1주일이나 간간히 고민해서 답을 찾아냄.
  • 일단 키 아이디어는 우선순위 큐를 써서 K의 개의 최대값을 찾는 문제로 바꾸는 것이다. 시간 복잡도를 $O(XY\log{K})$로 줄일수 있다.
  • Editorial에 보면 해법이 4가지나 있는데, 일본어라 도통 알수가 없다. 일단 $O(K\log{K})$같은 풀이가 보있는 것으로 보아 복습이 필요하다. ㅠㅠ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  int X, Y, Z, K;
  cin >> X >> Y >> Z >> K;
  typedef long long LL;
  
  vector<LL> A(X);
  vector<LL> B(Y);
  vector<LL> C(Z);
  for(int i = 0; i < X; i++) cin >> A[i];
  for(int i = 0; i < Y; i++) cin >> B[i];
  for(int i = 0; i < Z; i++) cin >> C[i];
  
  auto rev = [](LL a, LL b) { return a > b; };
  priority_queue<LL, vector<LL>, decltype(rev)> pq(rev);
  sort(A.begin(), A.end(), rev);
  sort(B.begin(), B.end(), rev);
  sort(C.begin(), C.end(), rev);
    
  for(int a = 0; a < X; a++) {
    for(int b = 0; b < Y; b++) {
      for(int c = 0; c < Z; c++) {
        LL cur = A[a] + B[b] + C[c];
        if(pq.size() < K) pq.push(cur);
        else {
          if (pq.top() < cur) {
            pq.push(cur);
            pq.pop();
          } else {
            break;
          }
        }
      }
    }
  }
  
  vector<LL> ans(K);
  for(int i = K-1; i >= 0 ; i--)
    ans[i] = pq.top(), pq.pop();
  for(int i = 0; i < K; i++)
    cout << ans[i];
}