CODE FESTIVAL 2015予選A C 8月31日

■■■問題■■■

とある星のとある8月31日のことです。
とある星の高橋君はあることに気づいてしまいました。
今日で夏休みが終わりであるにもかかわらず、宿題が全く終わっていないのです！

宿題のタイムリミットまではあとT分あります。
そして、高橋君がやらなければいけない宿題はN個あります。
i番目の宿題を高橋君が解くにはAi分かかりますが、
高橋君の友達である青木君が解いた宿題を丸写ししてしまうことでBi分で終わらせることもできます。

しかし友達の宿題を写すのはあまり良くないことなので、
高橋君はできるだけ写さないようにしたいと思っています。

タイムリミットまでに全ての宿題を終わらせるために
高橋君が写す必要のある宿題の個数の最小値を出力してください。
ただし、全ての宿題を写してもタイムリミットまでに終わらせることができない場合は
代わりに-1を出力してください。

■■■入力■■■

N T
A1 B1
A2 B2
・・・
AN BN


●1行目には、2つの整数 N(1 <= N <= 10万),T(0 <= T <= 10億) が空白区切りで与えられる。
  これは、宿題がN個あり、タイムリミットまでの時間がT分であることを表す。
●2行目からのN行には、宿題にかかる時間の情報が与えられる。
  このうち i(1 <= i <= N) 行目には、2 つの整数 Ai,Bi(0 <= Bi<Ai <= 1万) が空白区切りで与えられる。
  これは、i番目の宿題を高橋君が解くと Ai分かかり、
  写すと Bi分かかることを表す。Bi<Ai であることに注意せよ。

■■■出力■■■

T 分以内に全ての宿題を終わらせるために高橋君が写す必要のある宿題の個数の最小値を1行に出力せよ。
ただし、全ての宿題を写してもT分以内に終わらせることができない場合は
代わりに-1を出力せよ。
出力の末尾に改行を入れること。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 7");
            WillReturn.Add("1 0");
            WillReturn.Add("3 0");
            WillReturn.Add("5 0");
            WillReturn.Add("2 0");
            WillReturn.Add("4 0");
            //2
            //例えば、2番目と3番目の宿題を写せば 7(=1+0+0+2+4)分で
            //全ての宿題を終わらせることができます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1000000000");
            WillReturn.Add("5 0");
            //0
            //宿題を写さなくてもタイムリミットに間に合います。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 0");
            WillReturn.Add("100 99");
            //-1
            //宿題を写してもタイムリミットに間に合いません。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("3 11");
            WillReturn.Add("5 2");
            WillReturn.Add("6 4");
            WillReturn.Add("7 3");
            //2
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("6 92");
            WillReturn.Add("31 4");
            WillReturn.Add("15 9");
            WillReturn.Add("26 5");
            WillReturn.Add("35 8");
            WillReturn.Add("97 9");
            WillReturn.Add("32 3");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct TimeInfoDef
    {
        internal int Takahashi;
        internal int Aoki;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        int T = wkArr.Last();

        int TakahashiSum = 0; //高橋君の合計
        int AokiSum = 0; //青木君の合計

        var TimeInfoList = new List<TimeInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            TimeInfoList.Add(new TimeInfoDef() { Takahashi = wkArr[0], Aoki = wkArr[1] });
            TakahashiSum += wkArr[0];
            AokiSum += wkArr[1];
        }
        TimeInfoDef[] TimeInfoArr = TimeInfoList.OrderBy(X => X.Aoki - X.Takahashi).ToArray();

        if (TakahashiSum <= T) {
            Console.WriteLine(0);
            return;
        }
        if (T < AokiSum) {
            Console.WriteLine(-1);
            return;
        }

        //貪欲法で解く
        int CopyCnt = 0;
        for (int I = 0; I <= TimeInfoArr.GetUpperBound(0); I++) {
            CopyCnt++;
            TakahashiSum -= TimeInfoArr[I].Takahashi;
            TakahashiSum += TimeInfoArr[I].Aoki;
            if (TakahashiSum <= T) {
                break;
            }
        }
        Console.WriteLine(CopyCnt);
    }
}

解説

貪欲法で
青木君のを移したら短縮できる時間の多い宿題から、選択してます。