SRM492 Div1 Easy(250), Div2 Medium(550) TimeTravellingGardener

TopCoder

TimeTravellingGardener

答えがN-1未満なら少なくとも2本は元の高さのままなので、2本の木の組み合わせについて木の先端を結んだ線を候補として調べる。一番短い木にあわせて切れば少なくとも1本は切る必要が無い。

#include <vector>
using namespace std;

class TimeTravellingGardener{public:
int determineUsage( vector <int> distance, vector <int> height )
{
    int N = (int)height.size();
    vector<int> x(N);
    for ( int i=0; i<N-1; i++ )
        x[i+1] = x[i] + distance[i];
    vector<int> y = height;

    int ans = N-1;

    for ( int i=0; i<N; i++ )
    for ( int j=i+1; j<N; j++ )
    {
        bool f = true;
        int c = 0;

        for ( int k=0; k<N; k++ )
        if ( k != i  &&  k != j )
        {
            //  (y[k]-y[i]) > (y[j]-y[i])/(x[j]-x[i])*(x[k]-x[i])
            if ( (y[k]-y[i])*(x[j]-x[i]) > (y[j]-y[i])*(x[k]-x[i]) )
                c++;
            if ( (y[k]-y[i])*(x[j]-x[i]) < (y[j]-y[i])*(x[k]-x[i]) )
                f = false;
            if ( (0   -y[i])*(x[j]-x[i]) > (y[j]-y[i])*(x[k]-x[i]) )
                f = false;
        }

        if ( f )
            ans = min( ans, c );
    }

    return ans;
}};