焼く時間が長い順にソートしてから、2台の肉焼き機に振り分けた。
using System; using System.Linq; namespace ARC029A { class Program { static void Main(string[] args) { var N = int.Parse(Console.ReadLine()); var t = new int[N]; for (var i = 0; i < N; i++) { t[i] = int.Parse(Console.ReadLine()); } var descT = t.OrderByDescending(x => x).ToArray(); var grill1 = descT[0]; var grill2 = 0; for (var i = 1; i < descT.Length; i++) { var ti = descT[i]; if (grill1 + ti > grill2 + ti) { grill2 += ti; } else { grill1 += ti; } } var answer = Math.Max(grill1, grill2); Console.WriteLine(answer); } } }
でもこれ、よく考えると N 枚の肉を 2 台の肉焼き機のどちらで焼くかを、ビット全探索で調べればよかったな。別解。
using System; namespace ARC029A { class Program { static void Main(string[] args) { var N = int.Parse(Console.ReadLine()); var t = new int[N]; for (var i = 0; i < N; i++) { t[i] = int.Parse(Console.ReadLine()); } var answer = int.MaxValue; for (var bit = 0; bit < (1 << N); bit++) { var grill1 = 0; var grill2 = 0; for (var i = 0; i < t.Length; i++) { if ((bit & (1 << i)) != 0) { grill1 += t[i]; } else { grill2 += t[i]; } } answer = Math.Min(answer, Math.Max(grill1, grill2)); } Console.WriteLine(answer); } } }