「A - 高橋君とお肉」の簡単な解き方

AtCoderのA問題が解けない

A - 高橋君とお肉
A問題が解けなくて調べたら、
「bit全探索」を使用するとのことでした。

A問題だから簡単な解き方があるはずと試行錯誤しまして...
ソートを使ってシンプルに解くことができました。

解き方

各肉の調理時間を降順に並べて、
肉焼き器に調理時間を分配します。

#include<bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin >> N; // 肉の数
  vector<int> t(N); // 各肉の調理時間を格納する配列
  int sum1 = 0, sum2 = 0; // 2つの肉焼き器の合計調理時間
  
  // 各肉の調理時間を入力
  for(int i = 0; i < N; i++)
    cin >> t[i];
    
  // 調理時間を降順にソート
  sort(t.begin(), t.end(), greater<int>());
  
  // 2つの肉焼き器に調理時間を分配
  for(int i = 0; i < N; i++){
    if(sum1 > sum2)
      sum2 += t[i];
    else
      sum1 += t[i];
  }
  
  // 合計調理時間の大きい方を出力
  cout << max(sum1,sum2) << endl;
  return 0;
}