题目描述

数据范围

样例

input

9
1
1
2
2 1
3
3 2 1
4
7 1 5 3
5
11 2 15 7 10
6
1 8 2 16 8 16
2
624323799 708290323
12
2 1 1 3 3 11 12 22 45 777 777 1500
12
12 11 10 9 8 7 6 5 4 3 2 1

output

0
1
3
6
10
3
0
2
66

分析

如果直接暴力枚举，会超时；

只需要考虑相邻的两个需要变化几次，维护前缀和，
当前这个数所要修改的次数就是前面要修改的次数和后面要修改的次数求和，
当前修改的次数有可能是负的

#include <bits/stdc++.h>

#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e6 + 10;
const double eps = 1e-8;

int n;
ll a[N];



void solve()
{
    cin >> n;
    ll cnt = 0;
    for (int i = 0; i < n ; i ++) cin >> a[i];

    ll ans = 0;
    for (int i = 1; i < n ; i ++)
    {
        ll l = a[i - 1], r = a[i], ct = 0;//ct 表示是修改次数
        while(l < r) ct --, l *= 2;
        while(l > r) ct ++, r *= 2;

        cnt = max(0ll, cnt + ct);
        ans += cnt;    
    }

    cout << ans << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t --) solve();
    return 0;
}