GESP C++五级数论题解：贪心算法与二进制操作

狭间

1. 题目背景与理解

这道来自GESP C++五级认证的题目，考察的是数论基础与贪心算法的结合应用。题目要求我们通过最少的操作次数，将给定序列中的所有元素变得相等。每次操作允许我们将序列中的某个元素乘以2或者除以2（如果能被2整除）。

在实际编程竞赛和算法学习中，这类题目非常典型——它既考察了对数学规律的洞察力，又考验了将数学观察转化为有效算法的能力。作为五级认证的题目，它确实有一定挑战性，但通过系统分析完全可以掌握。

提示：这类题目往往存在"关键观察点"，一旦找到就能大幅简化问题。我们需要关注所有数字能否通过乘除2的操作达到某个共同值。

2. 问题分析与关键观察

2.1 操作的本质理解

首先我们需要明确题目中操作的本质特性：

乘以2操作：相当于在二进制表示后面添加一个0
除以2操作：相当于去掉二进制表示的最后一位（如果最后一位是0）

这意味着，所有操作都不会改变数字的"核心部分"——即去掉末尾所有0后的奇数部分。例如：

数字12（1100）的核心是3（11）
数字6（110）的核心也是3（11）
数字3（11）的核心就是它本身

2.2 关键数学性质

由此我们可以得出两个重要结论：

核心相同原则：只有当两个数字的核心相同时，才能通过一系列乘除2操作相互转换
操作可逆性：任何乘除2操作都可以通过逆向操作还原

这直接引出了解题的第一个必要条件：序列中所有数字的核心必须相同，否则题目无解。

2.3 解题思路推导

基于以上观察，我们的解题步骤应该是：

检查所有数字的核心是否相同
如果不同，直接返回无解
如果相同，计算将所有数字调整到同一数值的最小操作步数

3. 算法设计与实现

3.1 核心提取函数

首先我们需要实现一个函数来提取数字的核心：

cpp复制int getCore(int x) {
    while (x % 2 == 0) {
        x /= 2;
    }
    return x;
}

这个函数通过不断除以2，直到得到一个奇数，即为该数字的核心。

3.2 核心一致性检查

接下来检查所有数字的核心是否一致：

cpp复制bool checkCores(const vector<int>& nums) {
    if (nums.empty()) return true;
    int core = getCore(nums[0]);
    for (int num : nums) {
        if (getCore(num) != core) {
            return false;
        }
    }
    return true;
}

3.3 操作步数计算

这是最核心的部分。我们需要找到一个目标值，使得将所有数字调整到这个值所需的总操作步数最小。

3.3.1 关键思路

将所有数字不断除以2，直到它们不能再被2整除（即达到核心值）
记录每个数字在达到核心值过程中的"右移"次数
然后让所有数字从核心值开始，通过左移（乘以2）达到某个共同值
计算最优的共同值使得总操作步数最小

3.3.2 具体实现

cpp复制int minOperations(vector<int>& nums) {
    // 检查核心一致性
    if (!checkCores(nums)) return -1;
    
    // 记录每个数字的右移次数（除以2的次数）
    vector<int> shifts;
    for (int& num : nums) {
        int shift = 0;
        while (num % 2 == 0) {
            num /= 2;
            shift++;
        }
        shifts.push_back(shift);
    }
    
    // 现在所有num都等于核心值
    int core = nums[0];
    
    // 我们需要找到一个目标shift，使得总步数最小
    // 总步数 = Σ|shift_i - target|
    // 这是一个典型的求中位数问题
    sort(shifts.begin(), shifts.end());
    int target = shifts[shifts.size() / 2];  // 中位数
    
    int total = 0;
    for (int s : shifts) {
        total += abs(s - target);
    }
    
    return total;
}

3.4 复杂度分析

时间复杂度：O(n log n)，主要来自排序操作
空间复杂度：O(n)，用于存储右移次数

4. 完整代码实现

cpp复制#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getCore(int x) {
    while (x % 2 == 0) {
        x /= 2;
    }
    return x;
}

bool checkCores(const vector<int>& nums) {
    if (nums.empty()) return true;
    int core = getCore(nums[0]);
    for (int num : nums) {
        if (getCore(num) != core) {
            return false;
        }
    }
    return true;
}

int minOperations(vector<int>& nums) {
    if (!checkCores(nums)) return -1;
    
    vector<int> shifts;
    for (int& num : nums) {
        int shift = 0;
        while (num % 2 == 0) {
            num /= 2;
            shift++;
        }
        shifts.push_back(shift);
    }
    
    sort(shifts.begin(), shifts.end());
    int target = shifts[shifts.size() / 2];
    
    int total = 0;
    for (int s : shifts) {
        total += abs(s - target);
    }
    
    return total;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    int res = minOperations(nums);
    if (res == -1) {
        cout << "-1" << endl;
    } else {
        cout << res << endl;
    }
    
    return 0;
}