SRM548 Div1 Easy(250), Div2 Medium(500) KingdomAndTrees

TopCoder

KingdomAndTrees

二分探索。魔法の出力がxとして条件が満たせるかどうかを判定する場合、前の木よりも高くできないならば不可能。そうでなければ、なるべく木の高さを低くしていくのが最善。下のプログラムでは、pが前の木の高さ。

#include <vector>
using namespace std;

class KingdomAndTrees{public:
int minLevel( vector <int> heights )
{
    int n = (int)heights.size();
    long long l = 0;
    long long r = 1000000000LL;

    while ( l<r )
    {
        long long m = (l+r)/2;

        long long p = 0;
        bool ok = true;
        for ( int j=0; j<n; j++ )
        {
            if ( p+1 > heights[j]+m )
                ok = false;
            p = max(p+1,heights[j]-m);
        }

        if ( ok )  r = m;
        else       l = m+1;
    }

    return (int)l;
}};