BOJ 25406 - 식사 계획 세우기

BOJ 25406 - 식사 계획 세우기

이게 뭔문젠가 하고 초장부터 문제 잘못읽어서 꼬였다.

두 개의 set이나 priority queue를 관리한다.

• 하나는 현재 남은 수 들 중 가장 많은 원소의 개수와 그 숫자를 바로 얻어올 수 있게 관리한다.
• 하나는 현재 남은 수들 중 가장 빠른 인덱스에 위치한 수와 그 인덱스를 얻어올 수 있도록 관리한다.

채워야 할 배열이 길이 $n$ 이 남았을 때, $\left\lfloor \dfrac {n+1}2 \right\rfloor+1$ 개 이상이라면 최대한 그리디하게 배치해도 인접하는 수가 생기므로,

이것이 생기지 않도록 첫 번째 set에서 가장 큰 수가 이걸 처리해야 할 때라면 그때그때 처리해준다.

왜 그때그때 처리해줘도 되냐면 $\left\lfloor \dfrac {n+1}2 \right\rfloor$ 개라고 했을 때 이러한 개수를 가진 수가 남은 $n$ 개에서 두 개이상 존재함은 불가능하기 때문이다.

바로 처리해주어야 할 수가 없다면, 두 번째 set에서 가장 빨리 오는걸 골라준다.

만약 가장 빨리오는것이 이전에 썼던 수라면 그 다음 빨리 오는것을 골라주면 된다.

void fail() {  
   cout << -1;  
   exit(0);  
}  
int limit(int len) { return (len + 1) / 2; }  
  
void solve() {  
   int n;  
   cin >> n;  
   vi a(n), v;  
   fv(a);  
   v = a;  
   uniq(v);  
   for (int &i: a)i = lbi(v, i);  
   int V = sz(v);  
  
   vvi pos(V);  
   auto remain = [&](int i) { return sz(pos[i]); };  
   for (int i = n - 1; i >= 0; i--) pos[a[i]].pb(i);  
  
   auto cmp1 = [&](auto &a, auto &b) {  
      if (a.fi ^ b.fi) return a.fi > b.fi;  
      return a.se < b.se;  
   };  
   auto cmp2 = [&](auto a, auto b) {  
      if (a.fi ^ b.fi) return a.fi < b.fi;  
      return a.se < b.se;  
   };  
   set<pi, decltype(cmp1)> set1(cmp1);  
   set<pi, decltype(cmp2)> set2(cmp2);  
   for (int i = 0; i < V; i++) {  
      set1.insert({remain(i), i});  
      set2.insert({pos[i].back(), i});  
   }  
  
   vi ans;  
   for (int i = 0, last = -1; i < n; i++) {  
      // 이것보다 많으면 fail  
      debug(ans);  
      int remain_len = n - i;  
      int mx = limit(remain_len);  
  
      auto it1 = set1.begin();  
      auto it2 = set2.begin();  
      if (it1->fi > mx || (last != -1 && remain(last) > limit(remain_len - 1))) fail();  
  
      int nxt = -1;  
  
      if (it1->fi > limit(remain_len - 1)) {  
         nxt = it1->se;  
      } else {  
         nxt = it2->se;  
         if (nxt == last) {  
            it2++;  
            nxt = it2->se;  
         }  
      }  
      ans.pb(pos[nxt].back() + 1);  
      set1.erase({remain(nxt), nxt});  
      set2.erase({pos[nxt].back(), nxt});  
      pos[nxt].pop_back();  
      if (remain(nxt)) {  
         set1.insert({remain(nxt), nxt});  
         set2.insert({pos[nxt].back(), nxt});  
      }  
      last = nxt;  
   }  
   for (int i: ans) {  
      cout << i << ' ';  
   }  
}