SRM156 Div.2 Easy DiskSpace

コメントに『ブログ書くなら問題とこう！』的なアドバイスいただきましたが・・・

相変わらず、はてなの書き込み数稼ぎという側面からまぁ書きます(笑)

まぁ今日はどちらかというとMMというものはどのようなプログラムを書いていくべきなのか考えたいところですがさすがにそれは時間が・・・

二つの可能性

問題文省略。

この問題には二つのアプローチが考えられます。
一つは最初におもいつくusedの総和をtotalの大きいほうのドライブで引いていくというもの。
もう一つはフリーの部分にtotalの少ないドライブを割り当てていくもの。

もしかしたら出来るかもしれませんが、今回は二つめのアプローチがうまくいきました。

以下コード

class DiskSpace {
   public:
   int minDrives(vector <int> used, vector <int> total)
  {
	int sum = 0;
	for (int i=0; i<used.size(); i++)
		sum += total[i]-used[i];
	sort(total.begin(), total.end());
	int j = 0;
	for (int i=0; i<total.size(); i++) {
		// cout << sum << endl;
		sum -= total[i];
		if (sum < 0) {
			break;
		} else {
			j++;
		}
	}
	int res = total.size() - j;
	return res;
  }
};