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

SRM 560 Div2 Medium TomekPhone

問題

各キーの頻度と,各キーが割り当てられるボタンの数と最大割り当て可能数が与えられる.

同一のボタンに複数のキーが割り当てられる場合,"abc"が割り当てられたとすると,aは1回のキーストロークで,bは2回のキーストロークで,cは3回のキーストロークで表示することが出来る. キーストロークの総和が最小となるようにキーをボタンに割り当てた時のキーストロークの総和を答える問題.

解答

頻度が大きいキーをよりコストの小さいボタンに割り当てるのが最適.

class TomekPhone
{
public:
  int minKeystrokes(vector <int> frequencies, vector <int> keySizes)
    {
      int n = frequencies.size();
      int m = keySizes.size();
      int numKey = 0;
      int i;
      for(i = 0; i < m; i++) numKey += keySizes[i];
      if (numKey < n) return -1;
      sort(frequencies.rbegin(), frequencies.rend());
      sort(keySizes.rbegin(), keySizes.rend());
      // for(i = 0; i < n; i++){
      //   cout << frequencies[i] << ",";
      // }
      // cout << endl;
      int idx = 0;
      int cur_cost = 1;
      int res = 0;
      for(i = 0; i < n; i++){
        if (keySizes[idx] > 0){
          res += frequencies[i] * cur_cost;
          keySizes[idx]--;
          idx++;
        }
        if (idx >= m || keySizes[idx] == 0){
          idx = 0;
          cur_cost++;
        }
      }
      return res;
    }
};