BOJ 16209 - 수열 섞기

BOJ 16209 - 수열 섞기

덱을 이용한 그리디로 풀 수 있다.

인접한 수들의 합의 최대값은 덱에 가장 큰 수부터 넣고, 그 다음 큰수들부터 앞 뒤 앞 뒤로 붙여나가면 된다.

다만, $a_i < 0$ 인 것도 있으므로 음수 양수를 따로 분리해서 위와 같이 두 합칠 배열을 만들어준다.

음수 쪽에선 $a_i$가 가장 큰 것을 뒤로 가게 해주고, 양수 쪽에선 $a_i$ 가 가장 작은것을 앞으로 가게 해준다.

음수 + $0,0,\dots,0$ + 양수

배열처럼 합쳐주면 정답이다.

void solve() {  
   int n;  
   cin >> n;  
   vi a(n);  
   fv(a);  
   sort(all(a));  
   int zero = ubi(a, 0) - lbi(a, 0);  
   int minus = lbi(a, 0);  
   int plus = n - zero - minus;  
  
   vi negative(a.begin(), a.begin() + minus);  
   vi positive(a.begin() + zero + minus, a.end());  
  
   auto generate = [&](vi a) -> deque<int> {  
      for (int &i: a) i = abs(i);  
      sort(all(a), greater<>());  
      deque<int> b;  
      for (int i = 0; i < sz(a); i++) {  
         if (i & 1) b.push_back(a[i]);  
         else b.push_front(a[i]);  
      }  
      return b;  
   };  
  
   auto pos_dq = generate(positive);  
   auto neg_dq = generate(negative);  
   for (int &i: neg_dq) i *= -1;  
  
   if (sz(pos_dq) && pos_dq.front() > pos_dq.back()) reverse(all(pos_dq));  
   if (sz(neg_dq) && neg_dq.back() < neg_dq.front()) reverse(all(neg_dq));  
  
   for (int i: neg_dq) cout << i << ' ';  
   for (int i = 0; i < zero; i++) cout << 0 << ' ';  
   for (int i: pos_dq) cout << i << ' ';  
}