SRM 502 Div2 Easy TheProgrammingContestDivTwo

問題

プログラミングコンテストで各問題を制限時間T以内に解いていく.各問題を解く時間requiredTimeが与えられ,問題をt時間で解いた時のスコアは1増え,ペナルティとしてtが加算される.
制限時間内に問題を解いていき,ベストなスコアとその時のペナルティを返す.
# スコアが同じ場合より少ないペナルティを返す.

解答

スコアの増加はどの問題を解いても1増えるのに対し,ペナルティは累積した時間で算出されるので,早く解ける問題から解いていたほうが良い.requiredTimeをソートして小さい値から時間内に解ける問題を貪欲に選択していく.

class TheProgrammingContestDivTwo {
public:
  vector <int> find(int T, vector <int> requiredTime) {
    vector <int> res(2);

	sort(requiredTime.begin(), requiredTime.end());
    int n = requiredTime.size();
    int t = 0;
    res[0] = 0;
    res[1] = 0;
    for(int i = 0; i < n; i++){
      if(requiredTime[i] <= T){
        T -= requiredTime[i];
        t += requiredTime[i];
        res[0]++;
        res[1] += t;
      }else{
        break;
      }
    }
    return res;
  }
};