题解 | #游游的除2操作#

游游的除2操作

https://www.nowcoder.com/practice/b797f46aa75145a0bbe112099f7cbd18

解题思路

这是一道贪心题目。
关键思路：

由于每次操作只能除以2（向下取整），所以最终的相等值一定是数组中最小值经过若干次除以2得到的数
对于每个数，我们需要计算将其除以2多少次才能达到目标值
为了使操作次数最少，我们需要：
- 枚举所有可能的目标值（从最小值开始，每次除以2）
- 计算将所有数变成该目标值需要的操作次数
- 取所有方案中的最小值

代码

cpp
java
python

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

// 计算将num变成target需要的操作次数
int countOps(long long num, long long target) {
    if(num < target) return 1e9;  // 不可能的情况
    int ops = 0;
    while(num > target) {
        num /= 2;
        ops++;
    }
    return num == target ? ops : 1e9;
}

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    
    // 输入数组并找到最小值
    long long minVal = 1e18;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        minVal = min(minVal, a[i]);
    }
    
    long long ans = 1e18;
    // 枚举所有可能的目标值
    long long target = minVal;
    while(target > 0) {
        long long totalOps = 0;
        bool possible = true;
        
        // 计算将所有数变成target需要的操作次数
        for(int i = 0; i < n && possible; i++) {
            int ops = countOps(a[i], target);
            if(ops >= 1e9) possible = false;
            totalOps += ops;
        }
        
        if(possible) {
            ans = min(ans, totalOps);
        }
        target /= 2;
    }
    
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    // 计算将num变成target需要的操作次数
    static long countOps(long num, long target) {
        if(num < target) return (long)1e9;  // 不可能的情况
        int ops = 0;
        while(num > target) {
            num /= 2;
            ops++;
        }
        return num == target ? ops : (long)1e9;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        
        // 输入数组并找到最小值
        long minVal = Long.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            minVal = Math.min(minVal, a[i]);
        }
        
        long ans = Long.MAX_VALUE;
        // 枚举所有可能的目标值
        long target = minVal;
        while(target > 0) {
            long totalOps = 0;
            boolean possible = true;
            
            // 计算将所有数变成target需要的操作次数
            for(int i = 0; i < n && possible; i++) {
                long ops = countOps(a[i], target);
                if(ops >= 1e9) possible = false;
                totalOps += ops;
            }
            
            if(possible) {
                ans = Math.min(ans, totalOps);
            }
            target /= 2;
        }
        
        System.out.println(ans);
    }
}

def count_ops(num, target):
    # 计算将num变成target需要的操作次数
    if num < target:
        return float('inf')  # 不可能的情况
    ops = 0
    while num > target:
        num //= 2
        ops += 1
    return ops if num == target else float('inf')

n = int(input())
a = list(map(int, input().split()))

# 找到最小值
min_val = min(a)

ans = float('inf')
# 枚举所有可能的目标值
target = min_val
while target > 0:
    total_ops = 0
    possible = True
    
    # 计算将所有数变成target需要的操作次数
    for num in a:
        ops = count_ops(num, target)
        if ops == float('inf'):
            possible = False
            break
        total_ops += ops
    
    if possible:
        ans = min(ans, total_ops)
    target //= 2

print(ans)