题目描述

难度分:$1700$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

每次操作，你可以把一个$a[i]$变成$a[i] \times 2$。你需要使数组$a$非递减，也就是$a[i] \leq a[i+1]$。输出最少操作次数。

输入样例

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

输出样例

0
1
3
6
10
3
0
2
66

算法

贪心

贪心的策略很容易想到，从前往后贪，如果发现$a[i-1] \gt a[i]$，说明$a[i]$是需要倍增的。但遗憾的是，$a[i]$可能倍增的次数非常多，导致$long$ $long$也存不下，而且$python$的大数计算效率也堪忧，所以没办法偷鸡，只能想办法优化。

这里开辟一个$cnt$数组，$cnt[i]$表示$a[i]$倍增的次数。当比较$a[i-1]$和$a[i]$两个元素的大小关系时，要综合考虑$(a[i-1],cnt[i-1])$和$(a[i],cnt[i])$。比较的时候分为以下三种情况：

1. $cnt[i-1] \gt cnt[i]$，让$a[i-1]$倍增$cnt[i-1]-cnt[i]$次，中间只要$\gt a[i]$马上返回，由于遍历到$a[i]$时$cnt[i]=0$，所以受到$a[i] \leq 10^9$的限制，乘不了多少次就会返回false（返回true表示满足$a[i-1] \leq a[i]$）。如果没返回false，而是最后返回了true，也说明乘的次数不多，不影响效率。
2. $cnt[i-1] \lt cnt[i]$，让$a[i]$倍增$cnt[i]-cnt[i-1]$次，中间只要$\geq a[i-1]$马上返回true，否则最后返回false。
3. $cnt[i-1]=cnt[i]$，直接比较$a[i-1]$和$a[i]$。

如果比较$a[i-1]$和$a[i]$发现不满足单调不减，也需要分为以下两种情况来计算贡献：

1. $cnt[i-1] \leq cnt[i]$，此时有$a[i-1] \gt a[i] \times 2^{cnt[i]-cnt[i-1]}$，让$a[i]$在先倍增$cnt[i]-cnt[i-1]$次的基础上，看还需要倍增多少次可以超过$a[i-1]$，由于受到值域限制，这个过程会很快。
2. $cnt[i-1] \gt cnt[i]$，此时有$a[i-1] \times 2^{cnt[i-1]-cnt[i]} \gt a[i]$，假设$a[i-1]$最多倍增$t_1$次可以保证$a[i-1] \leq a[i]$成立，可以模拟求得$t_1$，而此时已经倍增了$cnt[i-1]-cnt[i]$次，所以多倍增了$cnt[i-1]-cnt[i]-t_1$次，$a[i]$也需要倍增相同的次数。但是也有可能原数组中满足$a[i] \lt a[i-1]$，所以还需要计算一下原始的$a[i]$倍增多少次可以超过原始的$a[i-1]$。假设为$t_2$次，那这种情况下对答案的贡献就是$cnt[i-1]-cnt[i]-t_1+t_2$。

复杂度分析

时间复杂度

遍历数组$a$的时间复杂度是$O(n)$，而对于每个$a[i]$，需要进行一系列的倍增操作，因受到值域$[1,10^9]$的限制，这个倍增操作大概就是几十次。因此，算法整体的时间复杂度为$O(nlog_2A)$，其中$A$就是值域的最大范围。

空间复杂度

除了输入的原数组$a$，还开辟了一个$cnt$数组，用于存储每个$a[i]$乘以$2$的次数。因此，算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, cnt[N];
LL a[N];

bool cmp(int i) {
    int cnt1 = cnt[i - 1], cnt2 = cnt[i];    // a[i-1]和a[i]分别乘了几次2
    int delta = abs(cnt1 - cnt2);
    if(cnt1 > cnt2) {
        LL res = a[i - 1];
        while(delta--) {
            res <<= 1;
            if(res > a[i]) return false;
        }
        return true;
    }else if(cnt1 < cnt2) {
        LL res = a[i];
        while(delta--) {
            res <<= 1;
            if(res >= a[i - 1]) return true;
        }
        return false;
    }else {
        return a[i - 1] <= a[i];
    }
}

LL solve() {
    if(n == 1) return 0;
    LL ans = 0;
    for(int i = 2; i <= n; i++) {
        if(!cmp(i)) {
            // a[i-1]>a[i]
            int x = cnt[i - 1], y = cnt[i];
            if(x <= y) {
                LL num = a[i];
                for(int j = 0; j < y - x; j++) {
                    num *= 2;
                }
                int t = 0;
                while(num < a[i - 1]) {
                    num *= 2;
                    cnt[i]++, t++;
                }
                ans += t;
            }else {
                LL num = a[i - 1];
                int t1 = 0;
                while(num*2 <= a[i]) {
                    num *= 2;
                    t1++;
                }
                num = a[i];
                int t2 = 0;
                while(num < a[i - 1]) {
                    num *= 2;
                    t2++;
                }
                cnt[i] += x - y - t1 + t2;
                ans += x - y - t1 + t2;
            }
        }
    }
    return ans;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            cnt[i] = 0;
        }
        printf("%lld\n", solve());
    }
    return 0;
}