ARC029A - 高橋君とお肉

atcoder.jp

焼く時間が長い順にソートしてから、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);
        }
    }
}