蓝桥杯 change 模拟

问题描述

　　数组A中共有n个元素，初始全为0。你可以对数组进行两种操作：1、将数组中的一个元素加1；2、将数组中所有元素乘2。求将数组A从初始状态变为目标状态B所需要的最少操作数。

输入格式

　　第一行一个正整数n表示数组中元素的个数
　　第二行n个正整数表示目标状态B中的元素

输出格式

　　输出一行表示最少操作数

样例输入

2
7 8

样例输出

7

数据规模和约定

　　n<=50，B[i]<=1000

这道题目挺好玩的。

正解是思考把B数组变为全为0的数组最少需要几步。

分析下如何把样例7 8 变为 0 0

先把奇数7减一，操作次数加一，偶数8不动，变为6 8

6 8都是偶数，都除以2，操作次数加一，变为3 4

奇数3减一，操作次数加一，变为 2 4

2 4都是偶数，都除以2，操作次数加一，变为1 2

奇数1减一，操作次数加一，变为0 2

0 2都是偶数，都除以2，操作次数加一，变为0 1

奇数1减一，操作次数加一，变为0 0

共操作7次

所以思路就是先遍历一遍B数组，把奇数全部减一，使得B数组全为偶数，然后所有元素都除以2。然后再遍历一遍B数组重复计算。

之前一直对while（1）这种写法很抵触，现在看来有时候特别方便。

参考自https://www.cnblogs.com/lusiqi/p/12547532.html

#include <bits/stdc++.h>
using namespace std;
int a[60];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    while (1) {
        for (int i = 1; i <= n; i++) {
            if (a[i] % 2 == 1) {
                ans++;
                a[i]--;
            }
        } 
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == 0) {
                cnt++;
            }
        }
        if (cnt == n) {
            break;
        }
        for (int i = 1; i <= n; i++) {
            a[i] /= 2;
            
        }
        ans++;
    }
    cout << ans << endl;   
    return 0;
}