AOJ 0659 展覧会

問題へのリンク(AOJ)
問題へのリンク(AtCoder)

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 4");
            WillReturn.Add("10 20");
            WillReturn.Add("5 1");
            WillReturn.Add("3 5");
            WillReturn.Add("4");
            WillReturn.Add("6");
            WillReturn.Add("10");
            WillReturn.Add("4");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2");
            WillReturn.Add("1 2");
            WillReturn.Add("1 2");
            WillReturn.Add("1 2");
            WillReturn.Add("1");
            WillReturn.Add("1");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 2");
            WillReturn.Add("28 1");
            WillReturn.Add("8 8");
            WillReturn.Add("6 10");
            WillReturn.Add("16 9");
            WillReturn.Add("4");
            WillReturn.Add("3");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8 8");
            WillReturn.Add("508917604 35617051");
            WillReturn.Add("501958939 840246141");
            WillReturn.Add("485338402 32896484");
            WillReturn.Add("957730250 357542366");
            WillReturn.Add("904165504 137209882");
            WillReturn.Add("684085683 775621730");
            WillReturn.Add("552953629 20004459");
            WillReturn.Add("125090903 607302990");
            WillReturn.Add("433255278");
            WillReturn.Add("979756183");
            WillReturn.Add("28423637");
            WillReturn.Add("856448848");
            WillReturn.Add("276518245");
            WillReturn.Add("314201319");
            WillReturn.Add("666094038");
            WillReturn.Add("149542543");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct SVInfoDef
    {
        internal long S;
        internal long V;
    }
    static List<SVInfoDef> mSVInfoLIst = new List<SVInfoDef>();

    static long[] mCArr;

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        long N = wkArr[0];
        foreach (string EachStr in InputList.Skip(1).Take((int)N)) {
            SplitAct(EachStr);
            SVInfoDef WillAdd;
            WillAdd.S = wkArr[0];
            WillAdd.V = wkArr[1];
            mSVInfoLIst.Add(WillAdd);
        }
        mSVInfoLIst = mSVInfoLIst.OrderByDescending(pX => pX.V).ThenByDescending(pX => pX.S).ToList();
        var Que = new Queue<SVInfoDef>(mSVInfoLIst);

        mCArr = InputList.Skip(1 + (int)N).Select(pX => long.Parse(pX)).ToArray();

        long Answer = 0;
        foreach (long EachC in mCArr.OrderByDescending(pX => pX)) {
            while (true) {
                if (Que.Count == 0) break;

                SVInfoDef Dequeued = Que.Dequeue();
                if (Dequeued.S <= EachC) {
                    Answer++;
                    break;
                }
                continue;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

まずは二分探索で考えます。

すると、K個の絵を展示するかの判定は、
額縁は、大きい順にK個選択するのが最適で、
あとは、絵を価値の降順に見ていき、
額縁に設定できる絵であれば、額縁とマッチングさせるのが最適と分かり、

二分探索ではなく、貪欲法で良いと分かります。