ARC144-B Gift Tax

問題へのリンク

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 2 2");
            WillReturn.Add("1 5 9");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2 3");
            WillReturn.Add("11 1 2");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 1 100");
            WillReturn.Add("8 5 6");
            //5
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("6 123 321");
            WillReturn.Add("10 100 1000 10000 100000 1000000");
            //90688
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mPlusVal;
    static long mMinusVal;
    static long[] mAArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mPlusVal = wkArr[1];
        mMinusVal = wkArr[2];

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        Array.Sort(mAArr); // 昇順にソートしておく

        long L = mAArr.Min();
        long R = mAArr.Max();

        // Rが達成可能な場合
        if (CanAchieve(R)) {
            Console.WriteLine(R);
            return;
        }

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

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

    // 全ての要素を、K以上にできるかを返す
    static bool CanAchieve(long pK)
    {
        long NeedMinusCnt = 0;

        foreach (long EachA in mAArr) {
            // 足す必要がある場合
            if (EachA < pK) {
                long Diff = pK - EachA;
                NeedMinusCnt += Diff / mPlusVal;
                if (Diff % mPlusVal > 0) {
                    NeedMinusCnt++;
                }
            }
        }

        foreach (long EachA in mAArr) {
            // 引くことが可能な場合
            if (EachA > pK) {
                long Diff = EachA - pK;
                if (Diff >= mMinusVal) {
                    NeedMinusCnt -= Diff / mMinusVal;
                }
            }
        }

        return NeedMinusCnt <= 0;
    }
}

解説

答えを二分探索してます。