SRM518 Div1 Medium - ConvexSequence

問題

長さnの数列aに対して「好きな要素を1減らす」という操作を行い、[1,n-2]の任意のiで a[i-1]+a[i+1]<=2a[i] が成り立つようにしたい
最低何回操作が必要か求める

解法

両端は操作しても損しかしないから考えなくていい
1<=i<=n-2の範囲を手前から見ていき、条件を満たしていない場合、要素を減らすことはできても増やすことはできないので、条件を満たすまでa[i]を減らし続けるしかない
a[i]で条件を満たすように減らすと今度はa[i-1]で条件を満たさなくなることもあるから、更新が止まるまでループ
最悪何回くらいループするか見積もりができてないままこれで出して通しちゃった
未だにわからないんだけどこれTLEさせるケースはあるのか？🤔あんまり解けた気がしてない

class ConvexSequence {
	public:
	ll getMinimum(vector<int> a) {
		ll n = a.size(), res = 0;
		while (1) {
			bool b = 0;
			reps(i,1,n-1) {
				ll t = max(0, (a[i]*2-a[i-1]-a[i+1]+1)/2);
				res += t, a[i] -= t, b += t;
			}
			if (!b) break;
		}
		return res;
	}
};