そろそろ1000点問題などもやりはじめる。

FanFailure

class FanFailure {
public:
  vector <int> getRange(vector <int> capacities, int minCooling) {
    int mfs=capacities.size();
    int mfc=capacities.size();
    vector <int> result;
    sort(capacities.rbegin(),capacities.rend());
    int rest = minCooling;
    for(int i = 0;i<capacities.size();++i) {
      rest -= capacities[i];
      mfs--;
      if (rest < 0) break;
    }

    sort(capacities.begin(),capacities.end());
    rest = minCooling;
    for(int i = 0;i<capacities.size();++i) {
      rest -= capacities[i];
      mfc--;
      if (rest < 0) break;
    }

特にこれといってはまるところはなし。

ChangePurse

class ChangePurse {
  int find_pos(vector <int> cointypes, int val){
    for(int i =0; i<cointypes.size();++i){
      if(val == cointypes[i]) return i;
    }
  }
public:
  vector <int> optimalCoins(vector <int> coinTypes, int value) {
    vector <int> cs = coinTypes;
    vector <int> mapped;
    vector <int> coins;
    vector <int> results;
    int num; 
    for(int i=0;i<coinTypes.size();++i) results.push_back(0);
    sort(cs.rbegin(),cs.rend());
    for(int k=0;k<cs.size();++k) mapped.push_back(find_pos(coinTypes,cs[k]));

    for(int j =0;j<cs.size();++j){
      if((value+1)%cs[j]==0){
    coins.push_back(value / cs[j]);
    value = cs[j]-1;
      }
      else {
    coins.push_back(0);
      }
    }
    coins.push_back(value);
    for(int z = 0;z<cs.size();++z) results[mapped[z]] = coins[z];
    return results;
  }

    result.push_back(mfs);
    result.push_back(mfc);
    return result;
  }

ベクタをソートする際にソート前のインデックスを覚えておきたい場合どうやるのがいいのかがわからん。