SRM 528 Div2 Medium Cut

問題

異なる長さのうなぎが与えられたとき,高々maxCut回うなぎを切って,長さが10となるうなぎの最大個数を求める問題

解答

長さが10の倍数かどうかで長さ10のうなぎを作れる個数が変わることに注意する.
10の倍数のほうが得られる個数が多いので10の倍数のものから切っていく.
また,切ることが出来る回数が制限されているので長さの小さい方から切っていく.

class Cut
{
public:
  int getMaximum(vector <int> eelLengths, int maxCuts)
    {
      vector<int> tens;
      vector<int> others;
      int i;
      int n = eelLengths.size();
      int ret = 0;
      for(i = 0; i < n; i++){
        if(eelLengths[i] % 10 == 0) tens.push_back(eelLengths[i]);
        else others.push_back(eelLengths[i]);
      }
      sort(tens.begin(), tens.end());
      // cout << "hoge" << endl;
      for(i = 0; i < tens.size(); i++){
        if ((tens[i] / 10) - 1 <= maxCuts){
          ret += tens[i] / 10;
          maxCuts -= tens[i] / 10 - 1;
        }else{
          return ret + maxCuts;
        }
      }
      // cout << "fuga" << endl;
      for(i = 0; i < others.size(); i++){
        if (others[i] / 10  <= maxCuts){
          ret += others[i] / 10;
          maxCuts -= others[i] / 10;
        }else{
          return ret + maxCuts;
        }
      }
      return ret;
    }
};