方法思路

这个问题可以通过以下步骤解决：

1. 首先，我们需要理解将一个数从0变到目标值x的最少操作次数。这个操作次数可以通过分析x的二进制表示来确定：
   • 二进制中1的个数表示需要执行多少次"+1"操作
   • 最高位1的位置表示需要执行多少次"×2"操作（相当于左移）
   • 总操作次数 = 1的个数 + 最高位位置
2. 然后，我们需要考虑如何最优地安排区间操作：
   • 如果相邻两个位置i和i+1，操作次数分别为p和q
   • 当p > q时，位置i+1可以与位置i共用所有操作，不需要额外操作
   • 当q > p时，位置i+1可以与位置i共用p次操作，但需要额外执行(q-p)次操作
3. 因此，最终的最少操作次数是：
   • 第一个元素的操作次数 + 所有相邻元素操作次数差值的正和

代码实现

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader代替Scanner提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] b = new int[n];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                b[j] = Integer.parseInt(st.nextToken());
            }
            
            sb.append(minOperations(b)).append("\n");
        }
        
        System.out.print(sb);
    }
    
    public static int minOperations(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        
        // 直接计算结果，不存储中间步骤数组
        int prevStep = step(arr[0]);
        int result = prevStep;
        
        for (int i = 1; i < arr.length; i++) {
            int currentStep = step(arr[i]);
            if (currentStep > prevStep) {
                result += currentStep - prevStep;
            }
            prevStep = currentStep;
        }
        
        return result;
    }
    
    // 计算从0变到x的最少操作次数
    private static int step(int x) {
        if (x == 0) {
            return 0;
        }
        
        // 计算二进制中1的个数
        int onesCount = Integer.bitCount(x);
        
        // 计算最高位1的位置
        int highestBit = 31 - Integer.numberOfLeadingZeros(x);
        
        return onesCount + highestBit;
    }
}

Python

def min_operations(arr):
    # 计算从0变到x的最少操作次数
    def step(x):
        if x == 0:
            return 0
        # 计算二进制中1的个数
        ones_count = bin(x).count('1')
        # 计算最高位1的位置
        highest_bit = x.bit_length() - 1
        return ones_count + highest_bit
    
    if not arr:
        return 0
    
    # 计算每个元素的最少操作次数
    steps = [step(x) for x in arr]
    
    # 计算最终结果
    result = steps[0]
    for i in range(1, len(steps)):
        if steps[i] > steps[i-1]:
            result += steps[i] - steps[i-1]
    
    return result

def solve():
    t = int(input())
    results = []
    
    for _ in range(t):
        n = int(input())
        b = list(map(int, input().split()))
        results.append(min_operations(b))
    
    for result in results:
        print(result)

solve()

C++

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

// 计算从0变到x的最少操作次数
int step(int x) {
    if (x == 0) {
        return 0;
    }
    
    // 计算二进制中1的个数
    int onesCount = __builtin_popcount(x);
    
    // 计算最高位1的位置
    int highestBit = 31 - __builtin_clz(x);
    
    return onesCount + highestBit;
}

int minOperations(vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }
    
    // 计算每个元素的最少操作次数
    vector<int> steps(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        steps[i] = step(arr[i]);
    }
    
    // 计算最终结果
    int result = steps[0];
    for (int i = 1; i < steps.size(); i++) {
        if (steps[i] > steps[i-1]) {
            result += steps[i] - steps[i-1];
        }
    }
    
    return result;
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> b(n);
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }
        
        cout << minOperations(b) << endl;
    }
    
    return 0;
}