AOJ 0539 Pizza

問題へのリンク

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("8");
            WillReturn.Add("3");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("1");
            WillReturn.Add("4");
            WillReturn.Add("6");
            WillReturn.Add("20");
            WillReturn.Add("4");
            WillReturn.Add("4");
            WillReturn.Add("12");
            WillReturn.Add("8");
            WillReturn.Add("16");
            WillReturn.Add("7");
            WillReturn.Add("7");
            WillReturn.Add("11");
            WillReturn.Add("8");
            WillReturn.Add("0");
            //3
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct InputInfoDef
    {
        internal int D;
        internal int[] DArr;
        internal int[] KArr;
    }

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

        var InputInfoList = new List<InputInfoDef>();

        int CurrInd = 0;
        while (true) {
            int d = int.Parse(InputList[CurrInd]);
            if (d == 0) break;

            InputInfoDef WillAdd;

            int n = int.Parse(InputList[CurrInd + 1]);
            int m = int.Parse(InputList[CurrInd + 2]);

            int StaInd1 = CurrInd + 3;
            int EndInd1 = CurrInd + 3 + (n - 1) - 1;

            int StaInd2 = EndInd1 + 1;
            int EndInd2 = StaInd2 + m - 1;

            var DList = new List<int>();

            // 店舗1の分 (原点)
            DList.Add(0); // 原点
            DList.Add(d); // 原点(環状の対応)
            for (int I = StaInd1; I <= EndInd1; I++) {
                DList.Add(int.Parse(InputList[I]));
            }
            DList.Sort();

            var KList = new List<int>();
            for (int I = StaInd2; I <= EndInd2; I++) {
                KList.Add(int.Parse(InputList[I]));
            }
            KList.Sort();

            WillAdd.D = d;
            WillAdd.DArr = DList.ToArray();
            WillAdd.KArr = KList.ToArray();
            InputInfoList.Add(WillAdd);

            CurrInd = EndInd2 + 1;
        }

        foreach (InputInfoDef EachInputInfo in InputInfoList) {
            Solve(EachInputInfo.DArr, EachInputInfo.KArr);
        }
    }

    static void Solve(int[] pDArr, int[] pKArr)
    {
        long Answer = 0;

        foreach (int EachK in pKArr) {
            int ResultInd = ExecNibunhou(EachK, pDArr);
            var KouhoList = new List<int>();
            KouhoList.Add(Math.Abs(EachK - pDArr[ResultInd]));
            KouhoList.Add(Math.Abs(EachK - pDArr[ResultInd + 1]));
            Answer += KouhoList.Min();
        }
        Console.WriteLine(Answer);
    }

    // 二分法で、引数以下で最大の値を持つ、添字を返す
    static int ExecNibunhou(int pBase, int[] pArr)
    {
        // 最後の要素が引数以下の特殊ケース
        if (pBase >= pArr.Last()) {
            return pArr.GetUpperBound(0);
        }
        // 最初の要素が引数未満の特殊ケース
        if (pBase < pArr[0]) {
            return 0;
        }

        int L = 0;
        int R = pArr.GetUpperBound(0);

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

            if (pArr[Mid] <= pBase) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

注文ごとに、
二分法で、一番近い店舗を求めてます。