非官方正经题解 | 擦黑板

一、核心思路深度拆解

要解决这个问题，我们首先要明确“最多能执行多少次全体除以2”的本质：
每次操作要求所有数都是偶数，等价于“所有数都能被2整除”。每执行一次操作，所有数都除以2，相当于对每个数的“2的幂次”减1。
当某一个数的“2的幂次”被减到0时（即该数变成奇数），就无法继续操作。因此：
最大操作次数 = 数组中每个数包含的“2的因子个数”的最小值。

举个直观的例子：
假设数组是 [8, 12, 40]：

• 8的2的因子个数：8 ÷2=4 → 4÷2=2 → 2÷2=1（共3次），即3个2；
• 12的2的因子个数：12÷2=6 →6÷2=3（共2次），即2个2；
• 40的2的因子个数：40÷2=20→20÷2=10→10÷2=5（共3次），即3个2；
  操作1次后：[4,6,20]（所有数仍为偶数，因为每个数的2的因子个数≥1）；
  操作2次后：[2,3,10]（此时12的2的因子已耗尽，3是奇数，无法继续）；
  因此最多操作2次，恰好是所有数2的因子个数的最小值。

二、代码逐行详细解释（带底层逻辑）

#include <bits/stdc++.h>  // 万能头文件：包含iostream（输入输出）、vector等常用库，无需单独引入
using namespace std;      // 命名空间：避免每次写std::cin/std::cout

int main() {
    // 变量定义：
    // n：存储输入的数字个数；mi：存储所有数的2的因子个数的最小值，初始化为200（因题目中N≤200，且10^9的2的因子最多30个，200足够大）
    int n, mi = 200;
    cin >> n;  // 读取数字个数（如样例1的3）
    
    // 遍历每个数字，计算其2的因子个数
    for (int i = 1; i <= n; i++) {  // i从1到n（共n次循环）
        int a, cnt = 0;  // a：存储当前读取的数字；cnt：计数当前数字的2的因子个数，初始为0
        cin >> a;        // 读取当前数字（如样例1的8、12、40）
        
        // 循环：只要a是偶数，就除以2并计数
        while (a % 2 == 0) {  // a%2==0 表示a是偶数
            cnt++;            // 2的因子个数+1
            a /= 2;           // a除以2（更新a的值，继续检查是否为偶数）
        }
        // 举例：a=12时，循环过程：
        // 第一次：12%2=0 → cnt=1，a=6；
        // 第二次：6%2=0 → cnt=2，a=3；
        // 第三次：3%2=1 → 退出循环，cnt=2（即12有2个2的因子）
        
        // 更新最小值：如果当前数的2的因子个数比mi小，就替换mi
        if (cnt < mi) {
            mi = cnt;
        }
        // 样例1的过程：
        // 第一个数8：cnt=3 → mi=3；
        // 第二个数12：cnt=2 → mi=2；
        // 第三个数40：cnt=3 → mi保持2；
    }
    
    cout << mi << endl;  // 输出最小值（即最大操作次数，样例1输出2）
    return 0;            // 程序正常结束
}

三、样例全流程模拟

样例1：输入 3 8 12 40

1. 初始化：n=3，mi=200；
2. 第一次循环（i=1）：
   • 读取a=8，cnt=0；
   • 8%2=0 → cnt=1，a=4；
   • 4%2=0 → cnt=2，a=2；
   • 2%2=0 → cnt=3，a=1；
   • 1%2≠0 → 退出循环；
   • cnt=3 < mi=200 → mi=3；
3. 第二次循环（i=2）：
   • 读取a=12，cnt=0；
   • 12%2=0 → cnt=1，a=6；
   • 6%2=0 → cnt=2，a=3；
   • 3%2≠0 → 退出循环；
   • cnt=2 < mi=3 → mi=2；
4. 第三次循环（i=3）：
   • 读取a=40，cnt=0；
   • 40%2=0 → cnt=1，a=20；
   • 20%2=0 → cnt=2，a=10；
   • 10%2=0 → cnt=3，a=5；
   • 5%2≠0 → 退出循环；
   • cnt=3 ≥ mi=2 → mi不变；
5. 输出mi=2 → 符合样例结果。

样例2：输入 4 5 6 8 10

1. 初始化：n=4，mi=200；
2. 第一次循环（i=1）：
   • 读取a=5，cnt=0；
   • 5%2≠0 → 退出循环；
   • cnt=0 < mi=200 → mi=0；
3. 后续循环（i=2/3/4）：
   • 6的cnt=1、8的cnt=3、10的cnt=1，均≥mi=0 → mi保持0；
4. 输出mi=0 → 符合样例结果。

四、关键细节与易错点

1. mi的初始值：
   • 初始值要足够大（如200），确保第一次比较时能被第一个数的cnt替换；
   • 若初始值设为0，会导致所有cnt都≥0，结果永远是0，错误。
2. a的更新：
   • 必须在循环内执行a /= 2，否则a永远是初始值，循环无限执行；
3. 奇数的处理：
   • 奇数的a%2=1，循环直接退出，cnt=0，这是正确的（奇数没有2的因子）。

五、扩展思考（为什么是“最小值”而非“最大值/平均值”）

• 最大值：若取最大值（如样例1的3），但第二个数12只能支撑2次操作，第3次操作时12已变成3（奇数），无法执行；
• 平均值：无实际意义，操作的前提是“所有数都满足条件”，只要有一个数不满足，就无法操作。

因此，只有最小值能准确反映所有数共同能支撑的最大操作次数。