解いた問題

2/18/2013

SRM569 Div1 Medium

500

O(n) の貪欲で解ける。
操作は、"Kの倍数を作る"、"全部上の階へ渡す"、"(倍数にならなくても)とにかく上の階から持ってくる"、の3パターンがある。
倍数を作れるなら極力そうした方が良いのは直感的に明らか。
m 階に注目しているとして、m 階に m - 1 階から幾人か上がってきている場合、彼らはその階で消費する必要がある。
その際、上の階からKの倍数にならないとしても全員を持ってきた方が、それより上の階で消費されるべき人数を減らせる。

苦戦した。貪欲は難しいと再認識した。


  1. class TheJediTest {  
  2. public:  
  3.   int minimumSupervisors(vector <int> v, int K)  
  4.   {  
  5.     const int N = v.size();  
  6.   
  7.     vector<int> u = v;  
  8.     for (int i = 0; i + 1 < N; ++i) {  
  9.       int req = (K - (u[i] % K)) % K;  
  10.       if (req <= v[i + 1]) {  
  11.         v[i + 1] -= req;  
  12.         u[i + 1] -= req;  
  13.         u[i] += req;  
  14.       } else {  
  15.         if (v[i] < u[i]) {  
  16.           u[i] += v[i + 1];  
  17.           v[i + 1] = 0;  
  18.           u[i + 1] = 0;  
  19.         } else {  
  20.           u[i + 1] += v[i];  
  21.           u[i] -= v[i];  
  22.           v[i] = 0;  
  23.         }  
  24.       }  
  25.     }  
  26.   
  27.     int sum = 0;  
  28.     for (int i = 0; i < N; ++i) {  
  29.       sum += (u[i] / K) + (bool)(u[i] % K);  
  30.     }  
  31.     return sum;  
  32.   }  
  33. };