问题描述

塔子哥是一位资深的程序员,他最近在研究一种特殊的数组操作。他有一个由正整数组成的数组,数组的长度是偶数。塔子哥可以对数组中的任意一个数字执行以下两种操作之一:

思路

统计 c0 为偶数的数量，c1 为奇数的数量，m = n / 2

• c0 == c1，答案为 0
• c0 < c1，选择 (c1 - m) 个奇数均进行一次乘2操作变成偶数，任选 (c1 - m) 个奇数即可
• c0 > c1，选择 (c0 - m) 个偶数进行下取整除法变成奇数，一定可以变成奇数，最差就是变成 1 选择哪些偶数进行下取整呢？ 就是下取整除法从偶数变成奇数的最小次数的前 (c0 - m) 个偶数即可

时间复杂度：$O(n\log n)$