BOJ 16368 - Working Plan

BOJ 16368 - Working Plan

혼란을 틈타 1등 코드가 되었다.

그냥 그리디 문제인데, 변수도 많고 구현이 헷갈릴 수 있다.

일단 어떤 사람이 최대 일할 수 있는 날은 $\left\lfloor \dfrac {n+h}{w+h} \right\rfloor$ 이다. 이것보다 많이 일하려는 일에 미친놈이 있으면 $-1$을 출력해주자.

그리고 항상 일할 때 $w$ 씩만 일하기 때문에 일을 $w$ 의 배수로 안하려는 파트타임잡들이 있다면 $-1$을 출력해주자.

위 조건은 사실 검사할 필요 없다. 제일 마지막에 모든 사람이 할 일이 $0$이 남았는지 체크해주는 것으로 위 조건까지 검사해줄 수 있다.

각각 사람들이 마지막으로 일한 시간 $last$ 배열을 관리하고 처음엔 $-\infty$로 초기화시킨다.

현재 $i$ 일이라 할 때, 현재 일하고 있는 사람 수는 $O(M)$에 $last_j \ge i-w+1$ 인 사람들의 수를 계산해주면 된다.

$d_i$ 보다 현재 일하고 있는 사람이 많으면 $-1$ 을 출력해준다.

필요한 사람의 수를 $need$ 라 하면, 지금 일을 할 수 있는 사람들은 $last_j \le i-w-h$ 인 $j$ 들이고,

일을 할 수 있는 사람의 수가 $need$ 보다 적다면 $-1$ 을 출력한다.

그렇지 않다면 $w_j$ 가 가장 많이 남은 사람들부터 일에 배치시킨다.

이 그리디가 성립하는 이유는 일을 더 적게 하는 사람이 먼저 배치되어있는 정답을 일을 더 많게 하는 사람이 배치되어있는 정답으로 항상 교체해줄 수 있기 때문이다.

그리고 마지막에 모두 $w_j$ 가 $0$이 되었는지 검사해주자.

시간복잡도는 $O(NM \log M)$ 이다.

void fail() {  
   cout << -1;  
   exit(0);  
}  
void solve() {  
   int m, n, w, h;  
   cin >> m >> n >> w >> h;  
   vi W(m), D(n + 1);  
   fv(W);  
   fv1(D);  
  
   vvi ans(m);  
   vi last_work(m, -1e9);  
   for (int i = 1; i <= n; i++) {  
      int current_working = 0;  
      for (int j = 0; j < m; j++) if (last_work[j] >= i - w + 1) current_working++;  
      if (current_working > D[i]) fail();  
      int need = D[i] - current_working;  
      vi cand;  
      for (int j = 0; j < m; j++) {  
         int available = last_work[j] <= i - w - h;  
         if (available) {  
            cand.pb(j);  
         }  
      }  
      // 더 해야할 일이 많은 사람부터 할당한다.  
      sort(all(cand), [&](int i, int j) {  
         return W[i] > W[j];  
      });  
      if (sz(cand) < need) fail();  
      for (int j = 0; j < need; j++) {  
         int person = cand[j];  
         last_work[person] = i;  
         ans[person].pb(i);  
         W[person] -= w;  
      }  
   }  
   for (int i = 0; i < m; i++) if (W[i] != 0) fail();  
  
   cout << 1 << endl;  
   for (int i = 0; i < m; i++) {  
      for (int j: ans[i]) cout << j << ' ';  
      cout << endl;  
   }  
}