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

SRM588 Div1 Easy GUMIAndSongsDiv1 (Div2 Medium GUMIAndSongsDiv2)

問題

Gumiは歌うことが大好きで,可能な限り多くの異なる歌を歌いたいと思っている.歌にはそれぞれ,歌うのにかかる時間duration[i]と,その歌を歌うのに必要な音階のtone[i]が設定されている.音階が違う歌は連続して歌うことは出来ず,xの歌を歌い終わって,yの歌を歌い始めるには|tone[x]-tone[y]|の準備時間が必要.
T秒与えられた時,Gumiが歌うことが出来る最大の曲数を求めよ.

解答

歌う順番を考えると,音階の準備時間が変わるので少々面倒.
予め歌う音階の幅をAからBに限定してしまえば,最適な準備時間は|B-A|となる.
歌う曲はT-|B-A|秒の間で音階AからBまでのdurationが小さい方からgreedyに選んでいけば良い.

class GUMIAndSongsDiv1
{
public:
  int maxSongs(vector <int> duration, vector <int> tone, int T)
    {
      vector<pair<int, int> > vs;
      int i, j, k;
      int n = tone.size();
      for(i = 0; i < n; i++){
        vs.push_back(make_pair(tone[i], duration[i]));
      }
      sort(vs.begin(), vs.end());
      int res = 0;

      for(i = 0; i < n; i++){
        for (j = i; j < n; j++){
          int min_tone = vs[i].first;
          int max_tone = vs[j].first;
          vector<int> costs;
          int c = max_tone - min_tone;
          for(k = i; k <= j; k++){
            costs.push_back(vs[k].second);
          }
          int v = 0;
          sort(costs.begin(), costs.end());
          // cout << "(" << i << ", " << j << ")" << endl;
          for (k = 0; k < costs.size(); k++){
            // cout << "," << costs[k];
            if (c + costs[k] > T) break;
            c += costs[k];
            v++;
          }
          // cout << endl;
          res = max(res, v);
        }
      }
      return res;
    }
};