SRM518 Div1 Medium(500) ConvexSequence

両隣の数より大きい数があれば小さくしていく。最大値が10⁹だけど、1ずつ小さくなっていくというようなことはないので、TLEはしない。

#include <string>
#include <vector>
using namespace std;

class ConvexSequence{public:
long long getMinimum( vector <int> a )
{
    int n = (int)a.size();
    long long ans = 0;

    while ( true )
    {
        bool f = true;
        for ( int i=1; i<=n-2; i++ )
        {
            int d = a[i] - (a[i-1]+a[i+1])/2;
            if ( d > 0 )
            {
                f = false;
                ans += d;
                a[i] -= d;
            }
        }
        if ( f )
            break;
    }

    return ans;
}};