BOJ 16368 - Working Plan
혼란을 틈타 1등 코드가 되었다.
그냥 그리디 문제인데, 변수도 많고 구현이 헷갈릴 수 있다.
일단 어떤 사람이 최대 일할 수 있는 날은 이다. 이것보다 많이 일하려는 일에 미친놈이 있으면 을 출력해주자.
그리고 항상 일할 때 씩만 일하기 때문에 일을 의 배수로 안하려는 파트타임잡들이 있다면 을 출력해주자.
위 조건은 사실 검사할 필요 없다. 제일 마지막에 모든 사람이 할 일이 이 남았는지 체크해주는 것으로 위 조건까지 검사해줄 수 있다.
각각 사람들이 마지막으로 일한 시간 배열을 관리하고 처음엔 로 초기화시킨다.
현재 일이라 할 때, 현재 일하고 있는 사람 수는 에 인 사람들의 수를 계산해주면 된다.
보다 현재 일하고 있는 사람이 많으면 을 출력해준다.
필요한 사람의 수를 라 하면, 지금 일을 할 수 있는 사람들은 인 들이고,
일을 할 수 있는 사람의 수가 보다 적다면 을 출력한다.
그렇지 않다면 가 가장 많이 남은 사람들부터 일에 배치시킨다.
이 그리디가 성립하는 이유는 일을 더 적게 하는 사람이 먼저 배치되어있는 정답을 일을 더 많게 하는 사람이 배치되어있는 정답으로 항상 교체해줄 수 있기 때문이다.
그리고 마지막에 모두 가 이 되었는지 검사해주자.
시간복잡도는 이다.
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;
}
}
Comments