O(n) の貪欲で解ける。
操作は、"Kの倍数を作る"、"全部上の階へ渡す"、"(倍数にならなくても)とにかく上の階から持ってくる"、の3パターンがある。
倍数を作れるなら極力そうした方が良いのは直感的に明らか。
m 階に注目しているとして、m 階に m - 1 階から幾人か上がってきている場合、彼らはその階で消費する必要がある。
その際、上の階からKの倍数にならないとしても全員を持ってきた方が、それより上の階で消費されるべき人数を減らせる。
苦戦した。貪欲は難しいと再認識した。
- class TheJediTest {
- public:
- int minimumSupervisors(vector <int> v, int K)
- {
- const int N = v.size();
- vector<int> u = v;
- for (int i = 0; i + 1 < N; ++i) {
- int req = (K - (u[i] % K)) % K;
- if (req <= v[i + 1]) {
- v[i + 1] -= req;
- u[i + 1] -= req;
- u[i] += req;
- } else {
- if (v[i] < u[i]) {
- u[i] += v[i + 1];
- v[i + 1] = 0;
- u[i + 1] = 0;
- } else {
- u[i + 1] += v[i];
- u[i] -= v[i];
- v[i] = 0;
- }
- }
- }
- int sum = 0;
- for (int i = 0; i < N; ++i) {
- sum += (u[i] / K) + (bool)(u[i] % K);
- }
- return sum;
- }
- };