题解 | #小红的乘2除2#

答案只会有3种情况， 一.在同一个数上作除2，乘2。 二.在相邻的数作除2，乘2。 三.在不相邻的数上作除2，乘2。 第1，2 种情况可以在O(n)的时间复杂度内解决，只需要计算变化量。 第3种情况对每个数的乘2和除2的变化量分别存到vector p1, p2中并排序，对每p1的的变化量在p2中从小到大找第一个不相邻的位置来更新，p1的每个数最多会在p2中找3个位置，所以复杂度也是O(n)。 总的时间复杂度是O(nlogn)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
const int N = 1e6+ 10;
ll n,m;
ll a[N];
void solve()
{
    cin >> n;
    vector<pi> p1, p2;
    for(int i = 1; i <= n; i++) cin >> a[i];
    a[0] = a[1], a[n + 1] = a[n];
    ll all = 0;    
    for(int i = 1; i < n; i++) {
        all += abs(a[i] - a[i + 1]);
    }
    ll res = 1e18;
    for(int i = 1; i <= n; i++) {
    	//预处理每个位置*2的变化量
        ll tem = 0, pre = 0;
        if(i > 1) tem += abs(a[i-1] - a[i] * 2), pre += abs(a[i] - a[i - 1]);
        if(i < n) tem += abs(a[i+1] - a[i] * 2), pre += abs(a[i + 1] - a[i]);
        p1.push_back({tem - pre, i});
        //预处理每个位置/2的变化量
        tem = 0, pre = 0;
        if(i > 1) tem += abs(a[i-1] - a[i] / 2), pre += abs(a[i] - a[i - 1]);
        if(i < n) tem += abs(a[i+1] - a[i] / 2), pre += abs(a[i + 1] - a[i]);
        p2.push_back({tem - pre, i});
        //第一种情况，在同一个位置上 *2 后再 /2
        tem = 0;
        pre = abs(a[i - 1] - a[i]) + abs(a[i] - a[i + 1]);
        ll t = (a[i] / 2) * 2;
        if(i > 1) tem += abs(a[i - 1] - t);
        if(i < n) tem += abs(t - a[i + 1]);
        res = min(res, all - pre + tem);
        if(i < n) {
        	//第二种情况，在相邻个位置上 *2 后再 /2，前一个 *2 ， 后一个 /2
            tem = 0, pre = (abs(a[i - 1] - a[i]) + abs(a[i] - a[i + 1]) + abs(a[i + 1] - a[i + 2]));
            ll t1 = a[i] * 2, t2 = a[i + 1] / 2;
            if(i > 1) tem += abs(a[i-1] - t1);
            tem += abs(t1 - t2);
            if(i + 1 < n)
                tem += abs(t2 - a[i + 2]);
            res = min(res, all - pre + tem);
            tem = 0;
            // 前一个 /2 ， 后一个 *2
            t1 = a[i] / 2, t2 = a[i + 1] * 2;
            if(i > 1) tem += abs(a[i-1] - t1);
            tem += abs(t1 - t2);
            if(i + 1 < n)
                tem += abs(t2 - a[i + 2]);
            res = min(res, all - pre + tem);
        }
    }
    sort(p1.begin(), p1.end());
    sort(p2.begin(), p2.end());
    // 第三种情况
    for(auto i: p1) { // 看起来复杂度像是O(n^2)，实际上第二层最多遍历3次。
        for(auto j: p2) {
            if(abs(i.second - j.second) > 1) {
                res = min(res, all + i.first + j.first);
                break;
            }
        }
    }
    cout << res;
}
int main()
{
  // 请在此输入您的代码
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
//     cin >> _;
    while(_--) solve();
}