题目
链接:https://ac.nowcoder.com/acm/contest/28886/1016
来源:牛客网时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld题目描述
在牛牛面前放着nnn个数,这些数字既有奇数也有偶数,只不过牛牛对奇数情有独钟,他特别想让这些数都变成奇数。
现在牛牛获得了一种能力,他可以执行一种操作:每次选中一个偶数,然后把这些数中与该数相等的数都除以2,例如现在有一个数组为[2,2,3][2,2,3][2,2,3],那么牛牛可以执行一次操作,使得这个数组变为[1,1,3][1,1,3][1,1,3]。
牛牛现在想知道,对于任意的nnn个数,他最少需要操作多少次,使得这些数都变成奇数?
示例1
输入
[复制](javascript:void(0)😉
3,[2,2,3]
返回值
[复制](javascript:void(0)😉
1
说明
只需做一次操作,会将其中的偶数2都变成1,满足了所有的数都是奇数的要求。
示例2
输入
[复制](javascript:void(0)😉
3,[1,3,7]
返回值
[复制](javascript:void(0)😉
0
说明
不需要做任何操作,因为所有的数原本就是奇数。
备注:
1≤n≤106,代表一个有多少数字1 \leq n \leq 10^{6},代表一个有多少数字1≤n≤106,代表一个有多少数字 a1,a2,a3...an(1≤ai≤109)代表数字的大小a_{1},a_{2},a_{3}...a_{n}(1 \leq a_{i} \leq 10^{9})代表数字的大小a1,a2,a3...an(1≤ai≤109)代表数字的大小 对于25%的数据,1≤n≤102,1≤ai≤103对于25\%的数据,1 \leq n \leq 10^{2},1 \leq a_{i} \leq 10^{3}对于25%的数据,1≤n≤102,1≤ai≤103 对于75%的数据,1≤n≤104,1≤ai≤106对于75\%的数据,1 \leq n \leq 10^{4},1 \leq a_{i} \leq 10^{6}对于75%的数据,1≤n≤104,1≤ai≤106 对于100%的数据,1≤n≤106,1≤ai≤109对于100\%的数据,1 \leq n \leq 10^{6},1 \leq a_{i} \leq 10^{9}对于100%的数据,1≤n≤106,1≤ai≤109
题解
set功能多:
插入
删除
最值
去重
查找
一条龙
代码
class Solution {
public:
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回一个数,代表让这些数都变成奇数的最少的操作次数 * @param n int整型 代表一共有多少数 * @param a int整型vector 代表n个数字的值 * @return int整型 */
int oddNumber(int n, vector<int>& a) {
// write code here
set<int>st;
int cnt = 0;
for (auto it = a.begin(); it != a.end();it++)
{
if (*it % 2 == 0)
{
st.insert(*it);
}
}
while (!st.empty())
{
cnt++;
auto it = st.end();
it--;
int tmp = *it;
st.erase(it);
tmp /= 2;
if (tmp%2 == 0)
{
st.insert(tmp);
}
}
return cnt;
}
};