AOJ 0704 展覧会 2

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3 1 34");
            WillReturn.Add("10 250");
            WillReturn.Add("30 200");
            WillReturn.Add("50 500");
            //500
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4 10");
            WillReturn.Add("21 160");
            WillReturn.Add("32 270");
            WillReturn.Add("11 115");
            WillReturn.Add("44 205");
            //115
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 4 14");
            WillReturn.Add("21 160");
            WillReturn.Add("32 270");
            WillReturn.Add("11 115");
            WillReturn.Add("44 205");
            //-1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("6 3 4");
            WillReturn.Add("4 2");
            WillReturn.Add("5 2");
            WillReturn.Add("2 1");
            WillReturn.Add("9 2");
            WillReturn.Add("1 1");
            WillReturn.Add("7 2");
            //1
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("15 6 129");
            WillReturn.Add("185 2821");
            WillReturn.Add("683 3312");
            WillReturn.Add("101 3406");
            WillReturn.Add("485 2120");
            WillReturn.Add("671 1992");
            WillReturn.Add("869 2555");
            WillReturn.Add("872 3123");
            WillReturn.Add("237 2970");
            WillReturn.Add("351 2374");
            WillReturn.Add("996 2090");
            WillReturn.Add("729 2686");
            WillReturn.Add("375 2219");
            WillReturn.Add("820 3085");
            WillReturn.Add("511 3217");
            WillReturn.Add("924 4229");
            //2219
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mM;
    static long mDistance;

    struct PosInfoDef
    {
        internal long Pos;
        internal long Value;
    }
    static List<PosInfoDef> mPosInfoList = new List<PosInfoDef>();

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

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

        SplitAct(InputList[0]);

        mM = wkArr[1];
        mDistance = wkArr[2];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PosInfoDef WillAdd;
            WillAdd.Pos = wkArr[0];
            WillAdd.Value = wkArr[1];
            mPosInfoList.Add(WillAdd);
        }
        mPosInfoList = mPosInfoList.OrderBy(pX => pX.Pos).ToList();

        // 0が達成不可な場合
        if (CanAchieve(0) == false) {
            Console.WriteLine(-1);
            return;
        }

        long L = 0;
        long R = long.MaxValue;

        while (L + 1 < R) {
            long Mid = R / 2;
            if (R < long.MaxValue) {
                Mid = (L + R) / 2;
            }

            if (CanAchieve(Mid)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        Console.WriteLine(L);
    }

    // Kagen以上の絵をM枚取れるかを判定
    static bool CanAchieve(long pKagen)
    {
        long TakeCnt = 0;
        long CurrPos = long.MinValue;
        foreach (PosInfoDef EachPos in mPosInfoList) {
            if (EachPos.Value < pKagen) continue;
            if (CurrPos + mDistance <= EachPos.Pos) {
                TakeCnt++;
                CurrPos = EachPos.Pos;
            }
        }

        return TakeCnt >= mM;
    }
}

解説

下限以上の絵をM枚取れるかは、貪欲法で調べることができます。
なので、下限を二分探索してます。