CODE FESTIVAL 2016 qual C - B: K個のケーキ

問題

個のケーキが種類ある。各種類個ずつ存在する。毎日1個ずつ食べるとして、全てのケーキを食べ終えたとき、前日と同じケーキを食べる回数の最小値を出力せよ。

• 
• 
• 

解法

できるだけ多くの余りがあるケーキを食べるが、前日と同じ場合、2番目に大きなケーキを食べるというシミュレーションをする。Editorialや多くの提出と違って頭は良くない(がACはする)。以下のシミュレーションはくらいかと思う。

int main() {
 
  int K, T; cin >> K >> T;
  vector<pair<int, int>> vs;
  rep(i, T) {
    int x; cin >> x;
    vs.push_back({x, i});
  }
 
  int last = -1;
  int N = vs.size();
  while(vs.size() > 1) { // T-1要素すべて消すまで回す。全体でO(K + T)
    sort(all(vs));
 
    for(int i=N-1; i>=N-2; i--) {
      if(last != vs[i].second) {
        if(vs[i].first > 0) {
          last = vs[i].second;
          vs[i].first --; // 1個ずつ食べる
          if(vs[i].first == 0) {
            vs.erase(vs.begin() + i); // T-1回しか実行されない
            N = vs.size();
          }
          break;
        }
      }
    }
  }
 
  cout << vs[0].first - 1 << endl;
  
  return 0;
}

感想

はじめpriority_queueを書いていたが「一度取り出して、ダメならもう一度取り出して、はじめに取り出したものは入れ直す」という処理になり若干面倒だと気づいたのでsortした。