読者です 読者をやめる 読者になる 読者になる

SRM 608 Div2 Medium MysticAndCandiesEasy

問題

SRM 608 - TopCoder Wiki

箱のなかにキャンディが入っている,個々の箱にいくつキャンディが入っているか知ることは出来ないが, 箱iのなかに入っている可能性のあるキャンディの最大数high[i]と,全ての箱のなかに入っているキャンディの総数Cを知ることが出来る. いま食べたいキャンディの数がXの時,選んだ箱のキャンディをすべて食べるとすると, 選ばなくてはいけない箱の最小数を求める問題.

解答

選んでない箱のキャンディの数の総和はC-Xを超えない. なぜならそれを超えてしまうと,選んだ箱のキャンディの総和がXに満たない場合が出てくるからだ. ということは上限の低い箱を選ばないようにした選び方が最適となる. そのような箱の数を計算する.

class MysticAndCandiesEasy
{
public:
  int minBoxes(int C, int X, vector <int> high)
    {
      sort(high.begin(), high.end());
      int n = high.size();
      for(int i = 0; i < n; i++){
        if (C - high[i] < X) return n-i;
        C -= high[i];
      }
      return 0;
    }
};