SRM 518 div1 med:ConvexSequence
SRM518の練習会に参加しました。easyとmed通せました。わーい。
easyは簡単だと思うので省略します。
解法
貪欲っぽい感じで解きました。
a[i]とa[i+1]の差をb[i]とします。
凸になるためには,bの配列が単調増加になっていることが必要十分です。
こうなるための最小操作回数を求めれば良いことになりました。
で,じゃあどうやるかってことになるんですが,例えばbが
1,1,0,2,2
だったとしましょう。
a[0]を1下げるという操作はb[0]を1下げてb[1]を1上げるという操作に相当します。よって,まず2,3個目の1,0を解決するためには
1,0,1,2,2
とするやり方と
1,1,1,1,1
とするやり方があります。
このときどっちを選ぶのが良いのか考えます。bは単調増加数列にしなければならないので,bの最初のほうの数字が小さくなる方が有利です。よって,前者のように2個目を下げて3個目を上げるやり方が最適です。
こんな感じでやると答えを求めることが出来ます。
class ConvexSequence { public: long long getMinimum(vector <int> a) { int n = a.size(); if (n <= 2) return 0ll; ll ans = 0; vector<ll> b(n-1); for (int i = 0; i < n-1; i++) b[i] = a[i+1]-a[i]; while (1) { bool update = false; for (int i = 0; i < n-2; i++) { if (b[i] > b[i+1]) { update = true; ll ch = (b[i]-b[i+1]+1) / 2; ans += ch; b[i] -= ch; b[i+1] += ch; } } if (!update) break; } return ans; } };