第3回PAST J 回転寿司

問題へのリンク

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("2 5");
            WillReturn.Add("5 3 2 4 8");
            //1
            //2
            //-1
            //2
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 10");
            WillReturn.Add("13 16 6 15 10 18 13 17 11 3");
            //1
            //1
            //2
            //2
            //3
            //1
            //3
            //2
            //4
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 30");
            WillReturn.Add("35 23 43 33 38 25 22 39 22 6 41 1 15 41 3 20 50 17 25 14 1 22 5 10 34 38 1 12 15 1");
            //1
            //2
            //1
            //2
            //2
            //3
            //4
            //2
            //5
            //6
            //2
            //7
            //6
            //3
            //7
            //6
            //1
            //7
            //4
            //8
            //9
            //6
            //9
            //9
            //4
            //4
            //10
            //9
            //8
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int[] mMaxArr;
    static int[] mAArr;

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

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mN = wkArr[0];

        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        mMaxArr = new int[mN];

        foreach (int EachA in mAArr) {
            int NibunhouResult = ExecNibunhou(EachA);
            if (NibunhouResult == -1) {
                Console.WriteLine(-1);
            }
            else {
                mMaxArr[NibunhouResult] = EachA;
                Console.WriteLine(NibunhouResult + 1);
            }
        }
    }

    // 二分法で、引数の寿司を食べる添字を返す
    static int ExecNibunhou(int pSushi)
    {
        if (mMaxArr[0] < pSushi) return 0;
        if (mMaxArr[mN - 1] >= pSushi) return -1;

        int L = 0;
        int R = mN - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (mMaxArr[Mid] >= pSushi) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return R;
    }
}

解説

初期状態で全員が美味しさ0の寿司を食べた状態と考えれば、
最後に食べた美味しさの配列は、広義単調減少になるので、
寿司ごとに、どの人が食べるかを、二分法で求めてます。