牛客编程巅峰赛S1第6场 - 青铜局 B题 - 牛牛爱奇数_.net

牛客编程巅峰赛S1第6场 - 青铜局 B题 - 牛牛爱奇数

题目链接：https://ac.nowcoder.com/acm/problem/207569

Description

在牛牛面前放着nn个数，这些数字既有奇数也有偶数，只不过牛牛对奇数情有独钟，他特别想让这些数都变成奇数。
现在牛牛获得了一种能力，他可以执行一种操作：每次选中一个偶数，然后把这些数中与该数相等的数都除以2，例如现在有一个数组为[2,2,3]，那么牛牛可以执行一次操作，使得这个数组变为[1,1,3]。
牛牛现在想知道，对于任意的nn个数，他最少需要操作多少次，使得这些数都变成奇数？

Sample Input

3,[2,2,3]

Sample Output

Interpretation

只需做一次操作，会将其中的偶数2都变成1，满足了所有的数都是奇数的要求。

Comment

1≤n≤10⁶，代表一共有多少数字
a1,a2,a3…an(1≤ai≤10⁹)代表数字的大小
对于25%的数据,1≤n≤10²,1≤ai≤10³
对于75%的数据,1≤n≤10⁴,1≤ai≤10⁶
对于100%的数据,1≤n≤10⁶,1≤ai≤10⁹

Solution

显然这n个数里给出的奇数是无意义的，重复出现的偶数，取其中一个，其它的也可以看成是无意义的。

Solution_1

将这些数放进优先队列里，每次拿出最大的偶数，除以二，再判断还是不是偶数，如果是，并且优先队列里没有这个数，将其放进优先队列。重复此操作，直到队列为空。用map来记录数在不在队列里。

Code

class Solution {
public:
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型vector 代表n个数字的值
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        // write code here
       priority_queue<int, vector<int>, less<int> > p;//大根堆
        map<int, int> v;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 == 0&&v[a[i]]==0) p.push(a[i]), v[a[i]] = 1;
        }
        while (!p.empty()) {
            int temp = p.top();
            p.pop();
            if ((temp / 2) % 2 == 0) {
                if (v[temp/2] == 0) p.push(temp/2);
                v[temp / 2] = 1;
            }
            ++ans;
        }
        return ans;
    }
};

Solution_2

用set来实现去重，无需map。同样，每次拿出最大的偶数，除以二，再判断还是不是偶数，如果是，将其插入到set中，会自动去重。重复此操作，直到set为空。

Code

class Solution {
public:
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型vector 代表n个数字的值
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        // write code here
       set<int> p;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 == 0) p.insert(a[i]);
        }
        while (!p.empty()) {
            auto i = --p.end();
            p.erase(*i);
            if (((*i) / 2) % 2 == 0) p.insert((*i) / 2);
            ++ans;
        }
        return ans;
    }
};