ABC-085-D Katana Thrower

■■■問題■■■

あなたが散歩していると、突然一体の魔物が出現しました。
幸い、あなたは N本の刀、刀1、刀2、・・・、刀N を持っていて、
次の二種類の攻撃を自由な順番で行うことができます。

●持っている刀のうち一本を振る。刀i (1 <= i <= N) を振ると、魔物はaiポイントのダメージを受ける。
  同じ刀を何度振ることもできる。
●持っている刀のうち一本を投げつける。
  刀i (1 <= i <= N) を投げつけると、魔物はbiポイントのダメージを受け、あなたはその刀を失う。
  すなわち、あなたは以後その刀を振ることも投げつけることもできなくなる。

魔物は、受けたダメージの合計がHポイント以上になると消滅します。
魔物を消滅させるには、最小で合計何回の攻撃が必要でしょうか。

■■■入力■■■

N H
a1 b1
・
・
・
aN bN

●1 <= N <= 10万
●1 <= H <= 10億
●1 <= ai <= bi <= 10億
●入力値はすべて整数である

■■■出力■■■

魔物を消滅させるために必要な最小の合計攻撃回数を出力せよ。

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("1 10");
            WillReturn.Add("3 5");
            //3
            //あなたは1本の刀を持っていて、
            //振ると3ポイントのダメージ、投げつけると5ポイントのダメージを与えられます。
            //刀を2回振ってから投げつけると 3+3+5=11 ポイントのダメージを与え、
            //合計3回の攻撃で魔物が消滅します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 10");
            WillReturn.Add("3 5");
            WillReturn.Add("2 6");
            //2
            //先ほどの刀に加えてもう1本別の刀もあり、
            //こちらは振ると2ポイントのダメージ、投げつけると6ポイントのダメージを与えられます。
            //両方の刀を投げつけると 5+6=11 ポイントのダメージを与え、2回の攻撃で魔物が消滅します。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 1000000000");
            WillReturn.Add("1 1");
            WillReturn.Add("1 10000000");
            WillReturn.Add("1 30000000");
            WillReturn.Add("1 99999999");
            //860000004
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("5 500");
            WillReturn.Add("35 44");
            WillReturn.Add("28 83");
            WillReturn.Add("46 62");
            WillReturn.Add("31 79");
            WillReturn.Add("40 43");
            //9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal int A;
        internal int B;
    }

    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 H = wkArr[1];

        var ABList = new List<ABInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            ABList.Add(WillAdd);
        }

        int MaxA = ABList.Max(X => X.A);
        int RestHP = H;
        int Answer = 0;

        foreach (ABInfoDef EachABInfo in ABList.OrderByDescending(X => X.B)) {
            if (EachABInfo.B <= MaxA) break;

            RestHP -= EachABInfo.B;
            Answer++;
            if (RestHP <= 0) break;
        }
        if (RestHP > 0) {
            if (RestHP % MaxA > 0) {
                Answer += RestHP / MaxA + 1;
            }
            else {
                Answer += RestHP / MaxA;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

刀を振る中での最大ダメージ以上の刀の投げつけを
ダメージの降順に計上してから、
刀を振る中での最大値で割り算してます。