小美的陡峭值操作【C++实现】

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    vector<long long> results;
    
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 特殊情况处理
        if (n == 1) {
            results.push_back(0);
            continue;
        }
        
        // 1. 计算初始陡峭值
        long long initial_steepness = 0;
        vector<long long> diffs;
        for (int i = 0; i < n - 1; i++) {
            long long diff = abs(a[i] - a[i+1]);
            initial_steepness += diff;
            diffs.push_back(diff);
        }
        
        // 2. 计算每个位置的左边界变化量和右边界变化量
        vector<long long> left_effect(n, 0);   // 作为区间左端点时的变化
        vector<long long> right_effect(n, 0);  // 作为区间右端点时的变化
        
        // 左边界影响：操作后与左邻居的差值变化
        if (n > 1) {
            for (int i = 1; i < n; i++) {
                long long orig = abs(a[i-1] - a[i]);
                long long modified = abs(a[i-1] - (a[i] + 1));
                left_effect[i] = modified - orig;
            }
        }
        
        // 右边界影响：操作后与右邻居的差值变化
        for (int i = 0; i < n - 1; i++) {
            long long orig = abs(a[i] - a[i+1]);
            long long modified = abs((a[i] + 1) - a[i+1]);
            right_effect[i] = modified - orig;
        }
        
        // 3. 寻找最优区间变化量
        long long min_delta = 0;
        // 先考虑单点操作
        for (int i = 0; i < n; i++) {
            long long delta = 0;
            if (i > 0) delta += left_effect[i];
            if (i < n - 1) delta += right_effect[i];
            min_delta = min(min_delta, delta);
        }
        
        // 再考虑区间操作（只计算边界变化）
        long long min_left = 0;
        for (int i = 0; i < n; i++) {
            // 当前点作为右端点的最优组合
            long long delta = min_left + right_effect[i];
            min_delta = min(min_delta, delta);
            
            // 更新左端点最小值
            if (i < n - 1) {
                min_left = min(min_left, left_effect[i]);
            }
        }
        
        results.push_back(initial_steepness + min_delta);
    }
    
    // 输出结果
    for (long long res : results) {
        cout << res << "\n";
    }
    
    return 0;
}