问题分析

一个数组是非递减的，意味着对于数组中的任意两个元素 $a_i$ 和 $a_{i+1}$，都有 $ a_i \leq a_{i+1} $。

我们的目标是通过最少的操作次数，使数组变成非递减数组。每次操作的规则是将数组中某个元素 $ a_i $ 乘以 2，从而增大 $ a_i $ 的值，以满足非递减条件。

简单的暴力解法

直观的解决方法是从左到右遍历数组。对于每一对相邻元素 $ a_{i-1} $ 和 $ a_i $，如果 $ a_{i-1} \leq a_i $，则不做任何处理；如果 $ a_{i-1} > a_i $，则将 $ a_i $ 乘以 2，直到 $ a_i \geq a_{i-1} $ 为止。

然而，这种方法的效率较低。原因在于，每次将 $ a_i $ 乘以 2 时，可能会让 $ a_i $ 变成非常大的数（在极端情况下可能达到 $ 2^n $ 的级别）。因此，直接进行乘法运算会导致程序运行时间过长。

优化思路

为了避免显式地对数组中的元素进行多次乘法操作，可以采用以下优化方法：使用指数形式表示每个元素的“增长次数”，而不是直接修改数组元素本身。

具体来说，我们可以将每个元素 $ a_i $ 表示为 $ a_i \cdot 2^{x_i} $，其中 $ x_i $ 表示该元素经过的加倍操作次数。在这种表示方法下，我们避免了直接进行乘法操作，而是通过调整 $ x_i $ 来控制每个元素的变化。

具体实现

假设我们已经计算出了 $ x_{i-1} $（前一个元素的指数），现在要计算 $ x_i $（当前元素的指数）。可以分为两种情况：

• 如果 $ a_{i-1} \leq a_i $：此时，当前元素 $ a_i $ 不需要加倍，只需保持 $ x_i = x_{i-1} $。我们可以继续调整 $ x_i $，直到满足 $ a_{i-1} \cdot 2 \leq a_i $ 为止。

• 如果 $ a_{i-1} > a_i $：此时，当前元素 $ a_i $ 需要加倍才能满足条件，通过增加 $ x_i $，直到 $ a_i \cdot 2^{x_i} \geq a_{i-1} $。

在实际操作中，我们并不会真正改变数组中的元素，而是用一个变量 $ x_i $ 来记录每个元素应乘以的倍数。

解决步骤

1. 从左到右遍历数组，维护一个当前元素的指数 $ x_i $。
2. 对于每一对相邻元素，检查是否满足非递减条件：
   • 如果 $ a_{i-1} \leq a_i $，不做任何修改，直接移动到下一个元素。
   • 如果 $ a_{i-1} > a_i $，则通过增加 $ x_i $ 来增大 $ a_i $，直到满足 $ a_i \geq a_{i-1} $。
3. 统计操作次数，即每次增加 $ x_i $ 的次数，最终得到所需的最小操作次数。

代码实现

#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const char nl = '\n';
const int N = 1e5 + 10;
int a[N];

int cnt(int a, int b, int c) {
    int x = c;
    while (x > 0 && a * 2 <= b) {
        x--;
        a *= 2;
    }
    while (a > b) {
        x++;
        b *= 2;
    }
    return x;
}

void solve() {
    int n;
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int kk = 0;
    for (int i = 2; i <= n; ++i) {
        int num = cnt(a[i - 1], a[i], kk);
        sum += num;
        kk = num;
    }
    cout << sum << nl;
}

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

题解.md