[Codeforces] Codeforces Round #688 (Div. 2) B. Suffix Operations

2020年12月5日2020年12月12日

問題

方針

まず初めに、\( a_1 \) に対して操作する必要はありません。\( a_1 \) に対して操作を行うということは、全ての配列に対して \( 1 \) を加算または減算をするためです。操作の前に配列の値を変えない場合に必要な操作回数 \( b \) は、

\[ b = \sum_{i=1}^{n-1}|a_{i+1} – a_{i}|\]

となります。ここで、配列の値を \( 1 \) つ変えたときの必要な操作回数を考えます。\( a_1 \leftarrow a_2 \) とすると、\( b – |a_2 – a_1| \) となります。また、\( a_n \leftarrow a_{n-1} \) とすると、\( b – |a_{n} – a_{n – 1}| \) となります。\( 2 \leq i \leq n – 1 \) を満たす \( a_i \) を変えるとき、\( a_{i-1} \) または \( a_{i + 1} \) に変えることが考えられますが、どちらに変えたとしても、必要な操作回数は、

\[b – (|a_{i} – a_{i+1}| + |a_{i+1} – a_{i}|) + |a_{i + 1} – a_{i – 1}|\]

となります。したがって、全探索によって答えを求めます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int n;
ll a[200000]{};

void solve() {
    ll cnt = 0;
    ll c = max(abs(a[1] - a[0]), abs(a[n - 1] - a[n - 2]));
    for (int i = 1; i < n - 1; i++) {
        chmax(c, abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]) - abs(a[i + 1] - a[i - 1]));
    }
    for (int i = 1; i < n; i++) {
        cnt += abs(a[i - 1] - a[i]);
    }
    
    cout << cnt - c<< "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        solve();
    }

    return 0;
}