メモ

自分に向けて書いたメモを取り扱っています.

SRM 548 KingdomAndTrees

問題概要

数列xが与えられる.
x[i]を[max(1, x[i] - m), x[i] + m]の範囲で置き換えることができる.
xが単調増加になることを満たす時の最小のmを求める.

方針

二分探索でmを求める.
mで単調増加な数列が作れるかどうかは貪欲に求まる.

class KingdomAndTrees
{
    bool C(vector <int>& heights, int m)
    {
        int prev = max(heights[0] - m, 1);

        for(int i = 1; i < heights.size(); i++)
        {
            if(heights[i] + m < prev + 1)
                return false;
            else
                prev = max(prev + 1, heights[i] - m);

        }

        return true;
    }

    public:

    int minLevel(vector <int> heights)
    {
        int left = 0, right = 1000000000, mid;

        while(left < right)
        {
            mid = (left + right) / 2;

            if(C(heights, mid))
                right = mid;
            else
                left = mid + 1;
        }

        return left;
    }
};