SRM518 Div1 Medium

500

とりあえず条件の通りに実装して終わり。

"どうせこんな感じだろう"で通してしまった。
正答率を見て問題を選んでいることを後悔した。


他の解法もあるそうなので考えてみよう。

view plainprint?

1. class ConvexSequence {  
2. public:  
3.   long long getMinimum(vector <int> a)  
4.   {  
5.     const int N = a.size();  
6.     lli ret = 0;  
7.   
8.     while (true) {  
9.       lli tmp = ret;  
10.       for (int i = 1; i < N - 1; ++i) {  
11.         int b = min(a[i], (a[i - 1] + a[i + 1]) / 2);  
12.         ret += abs(a[i] - b);  
13.         a[i] = b;  
14.       }  
15.       if (tmp == ret) break;  
16.     }  
17.   
18.     return ret;  
19.   }  

class ConvexSequence {
public:
  long long getMinimum(vector <int> a)
  {
    const int N = a.size();
    lli ret = 0;

    while (true) {
      lli tmp = ret;
      for (int i = 1; i < N - 1; ++i) {
        int b = min(a[i], (a[i - 1] + a[i + 1]) / 2);
        ret += abs(a[i] - b);
        a[i] = b;
      }
      if (tmp == ret) break;
    }

    return ret;
  }