问题分析

小红有一个整数数组，要求在数组元素上执行最多两次操作（选择一个元素，使其加1），使得数组元素乘积的二进制末尾0的个数尽可能多。我们需要找出操作后的最优方案，返回二进制末尾0的最大数量。

二进制末尾0的概念

二进制末尾0的数量，实际上就是数字中包含因子2的个数。换句话说，数字中2的幂次方能分解出多少个2。

例如：

• 4的二进制是100，末尾有2个0，说明4 = 2^2。
• 8的二进制是1000，末尾有3个0，说明8 = 2^3。

因此，要使得数组元素乘积的二进制末尾有更多的0，我们需要尽量让每个数包含更多的因子2。

题解思路

1. 分析因子2的个数： 对每个数组元素，计算其包含的因子2的个数。通过将数不断除以2，直到不能再整除为止，统计次数。

2. 操作的意义： 操作的目标是增加因子2的数量。通过将数组元素加1来增加因子2的数量。要注意，如果加1后，原来数中的因子2数量会发生变化，因此要分析每个数加1后的情况。

3. 最大化末尾0的数量： 为了最大化末尾0的数量，我们首先记录下每个数当前的因子2个数，然后尝试对每个数进行加1操作，计算加1后因子2个数的变化，最终选择加1操作的最优位置。

4. 具体步骤：

   • 计算原始数组每个元素的因子2个数。
   • 如果一个数加1后能获得更多的因子2，则进行加1操作。
   • 尝试进行最多两次加1操作，最终计算操作后的最大末尾0数量。

复杂度分析

• 对于每个数，计算其因子2个数的时间复杂度是O(log a_i)，其中a_i是数组中的一个元素。对于n个元素，总时间复杂度是O(n log A)，其中A是数组元素的最大值。
• 总体来说，算法时间复杂度为O(n log A)，适用于n最大为10^5，a_i最大为10^9的情况。

代码实现

Python实现

# 输入处理
n = int(input())  # 数组大小
a = list(map(int, input().split()))  # 数组元素

# 计算一个数的因子2的个数
def count_factors_of_2(x):
    count = 0
    while x % 2 == 0:
        count += 1
        x //= 2
    return count

# 记录每个数的因子2个数
factor_2_count = [count_factors_of_2(x) for x in a]

# 记录加1后的因子2个数变化
increase_factor_2 = []

# 对每个数分析加1后的因子2个数
for x in a:
    new_x = x + 1
    original_factors = count_factors_of_2(x)
    new_factors = count_factors_of_2(new_x)
    increase_factor_2.append(max(new_factors - original_factors,0))

# 排序增加因子2的效果，选择前两个增加最大的
increase_factor_2.sort(reverse=True)

# 计算原始因子2总数
total_factor_2 = sum(factor_2_count)

# 对增加的因子2进行最多两次操作
max_increase = sum(increase_factor_2[:2])

# 输出结果
print(total_factor_2 + max_increase)

Java实现

import java.util.*;

public class Main {
    // 计算一个数的因子2的个数
    public static int countFactorsOf2(int x) {
        int count = 0;
        while (x % 2 == 0) {
            count++;
            x /= 2;
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 数组大小
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();  // 数组元素
        }

        // 记录每个数的因子2个数
        int[] factor2Count = new int[n];
        for (int i = 0; i < n; i++) {
            factor2Count[i] = countFactorsOf2(a[i]);
        }

        // 记录加1后的因子2个数变化
        List<Integer> increaseFactor2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int originalFactors = countFactorsOf2(a[i]);
            int newFactors = countFactorsOf2(a[i] + 1);
            increaseFactor2.add(Math.max(newFactors - originalFactors, 0));
        }

        // 排序增加因子2的效果，选择前两个增加最大的
        Collections.sort(increaseFactor2, Collections.reverseOrder());

        // 计算原始因子2总数
        int totalFactor2 = 0;
        for (int i = 0; i < n; i++) {
            totalFactor2 += factor2Count[i];
        }

        // 对增加的因子2进行最多两次操作
        int maxIncrease = 0;
        for (int i = 0; i < Math.min(2, increaseFactor2.size()); i++) {
            maxIncrease += increaseFactor2.get(i);
        }

        // 输出结果
        System.out.println(totalFactor2 + maxIncrease);
    }
}

C++实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计算一个数的因子2的个数
int countFactorsOf2(int x) {
    int count = 0;
    while (x % 2 == 0) {
        count++;
        x /= 2;
    }
    return count;
}

int main() {
    int n;
    cin >> n;  // 数组大小
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];  // 数组元素
    }

    // 记录每个数的因子2个数
    vector<int> factor2Count(n);
    for (int i = 0; i < n; i++) {
        factor2Count[i] = countFactorsOf2(a[i]);
    }

    // 记录加1后的因子2个数变化
    vector<int> increaseFactor2;
    for (int i = 0; i < n; i++) {
        int originalFactors = countFactorsOf2(a[i]);
        int newFactors = countFactorsOf2(a[i] + 1);
        increaseFactor2.push_back(max(newFactors - originalFactors, 0));
    }

    // 排序增加因子2的效果，选择前两个增加最大的
    sort(increaseFactor2.rbegin(), increaseFactor2.rend());

    // 计算原始因子2总数
    int totalFactor2 = 0;
    for (int i = 0; i < n; i++) {
        totalFactor2 += factor2Count[i];
    }

    // 对增加的因子2进行最多两次操作
    int maxIncrease = 0;
    for (int i = 0; i < min(2, (int)increaseFactor2.size()); i++) {
        maxIncrease += increaseFactor2[i];
    }

    // 输出结果
    cout << totalFactor2 + maxIncrease << endl;

    return 0;
}

题目内容

小红拿到了一个数组，她可以进行最多两次操作：选择一个元素，使其加$1$。

小红希望操作结束后，数组所有元素乘积的二进制末尾有尽可能多的$0$。你能帮帮她吗?

输入描述

第一行输入一个正整数$n$，代表数组的大小。

第二行输入$n$个正整数$a_i$，代表数组的元素。

$1≤n≤10^5$

$1≤a_i≤10^9$

输出描述

输出一个整数，代表操作结束后，数组所有元素乘积的二进制末尾$0$的数量。

样例1

输入

5
1 2 3 4 5 

输出

6

说明

操作两次后数组变为$[2,2,4,4,5]$，数组乘积为$320$,

二进制表示为$101000000$，有$6$个$0$。