SRM 622 Div2 Medium BoxesDiv2

問題

SRM 622 - TopCoder Wiki

candyを2xのサイズの箱に入れる. 異なる種類のcandyは異なる種類の箱に入れなくてはいけない. 箱2つは,その2つがすっぽり入るようなより大きい箱に入れることが出来る. 最終的に1つの箱にすべていれこむ時の最小の箱のサイズを求める問題.

解答

  • 初期化として,異なるcandyをそれぞれ最小の箱に詰めたと仮定する.
  • 任意の箱のペアを新しい大きな箱に入れたとすると,入力サイズが1小さくなった問題に帰着できる.
  • 後はどのペアを選択するか.
  • できるだけ小さな箱を作りたいので最小の箱2つを選択するのが最適.
class BoxesDiv2
{
public:
  int findSize(vector <int> candyCounts)
    {
      sort(candyCounts.begin(), candyCounts.end());
      int n = candyCounts.size();
      int i, j;
      // int curSize = 1;
      vector<int>boxes;
      for (i = 0; i < n; i++){
        for (j = 1; j < candyCounts[i]; j*=2);
        boxes.push_back(j);
      }
      // sort(boxes.rbegin(), boxes.rend());
      while (boxes.size() > 1) {
        sort(boxes.rbegin(), boxes.rend());
        int new_box = max(boxes.back(), boxes[boxes.size()-2]) << 1;
        boxes.pop_back();
        boxes.pop_back();
        boxes.push_back(new_box);
      }
      return boxes[0];
    }
};