SRM569 Div1 Medium

500

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;
  }
};