统计 c0 为偶数的数量,c1 为奇数的数量,m = n / 2
时间复杂度:O(nlogn)
小红是一位资深的程序员,他最近在研究一种特殊的数组操作。他有一个由正整数组成的数组,数组的长度是偶数。小红可以对数组中的任意一个数字执行以下两种操作之一:
小红的目标是通过一系列操作,使得最终数组中恰好一半的数字是奇数,另一半是偶数。他希望找到一种方案,使得操作次数最少。
输入的第一行包含一个正偶整数 n,表示数组的长度。
第二行包含 n 个正整数 A1,A2,…,An,表示初始的数组。
输出一个整数,表示达成目标所需的最少操作次数。
6
1 1 4 5 1 4
1
初始数组为 [1,1,4,5,1,4]。将第四个数字 5 除以 2 并向下取整,得到 [1,1,4,2,1,4],此时数组中恰好一半是奇数,另一半是偶数。
对于所有评测用例,满足 2≤n≤105,1≤Ai≤109,并且 n 是偶数。