题目思路

原题的答案有问题，有一种简单的方法是求出每个数最少需要多少次变换从0得到，求出最大的数量，然后每次都[1, n]所有元素进行操作，执行最大数量就可以得到结果，那些所需操作更少的数只需要在一开始为0的时候不停的乘以2即可，这样就还是0.

但是原题可能认为第一个操作不能是乘以2，所以只能通过相邻两个数的操作次数的差值来求解，假设第i个数的操作次数是x，第i+1个数的操作次数为y，如果y大于x，那么i+1和i这两个数可以共用x次操作，还需要y-x次的操作。如果y小于x，那么y就可以共享所有x的操作，这里记差值为0。所以直接将相邻数的操作次数的差值累加即可。

关于每个数的操作次数：只需要将每个数的二进制的1的数量和其最大位的位置相加即可，1的数量对应于+1，最大位置意味着*2（左移一位）。

代码

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int t = 0; t < T; t++) {
            int n = scanner.nextInt();
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                b[i] = scanner.nextInt();
            }

            int last = 0, ans = 0;
            for (int v : b) {
                int cnt = 0;
                while (v > 0) {
                    if (v % 2 == 1) {
                        v -= 1;
                    } else {
                        v /= 2;
                    }
                    cnt++;
                }
                if (cnt > last) {
                    ans += cnt - last;
                }
                last = cnt;
            }
            System.out.println(ans);
        }
    }
}

C++

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

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];
        }

        int last = 0, ans = 0;
        for (int v : b) {
            int cnt = 0;
            while (v > 0) {
                if (v % 2 == 1) {
                    v -= 1;
                } else {
                    v /= 2;
                }
                cnt++;
            }
            if (cnt > last) {
                ans += cnt - last;
            }
            last = cnt;
        }
        cout << ans << endl;
    }

    return 0;
}

Python

T = int(input())
for _ in range(T):
    n = int(input())
    b = list(map(int, input().split()))
    last, ans = 0, 0
    for v in b:
        cnt = 0
        while v:
            if v % 2 == 1:
                v -= 1
            else:
                v //= 2
            cnt += 1
        if cnt > last:
            ans += cnt - last
        last = cnt
    print(ans)

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

小红有一个长度为n且值都为0的数组a。对于这个致组小红每次操作可以选择一个区间[l, r]，对于[l,r]上的每一个数牛必须让其加一或者乘二(元素之间操作独立，可以选择些元素乘二，一些元素加一，但是区间内每个元素都要操作)

小红还有一个目标数组b，小红想知道对于初始数组a来说，其最少操作多少次可以将其变为b呢。

输入描述

第一行为，表示有t组数据

接下来有2t行，每组数据的第一行为一个n，第二行为n个整数，表示目标数组的元素b $1<=t<=10, 1<=n<=10^5, 1<=b_i<=10^9, \sum n<=10^5$

输出描述

输出为t行，每行为一组答案表示小红的最小操作次数

样例

输入

2
5
1 1 2 1 1
5
1 2 3 4 5

输出

2
4

说明 说明 第一组数据中，小红第一次选择区间[1,5]，让区间内所有元素加一，第二次小红选择区间[3,3]，让元素乘二。

第二组数据中，小红第一次选择区间(1,5]，让区间内所有元素加一。第二次小红选择区间[2,5]，让区间元素加一。第三次小红选择区间[3,5]，让a3加一，让a4,a5乘二。第四次小红选择区间[5,5]，让元素加一