牛牛满意的数组(二）

[编程题]牛牛满意的数组(二）

热度指数：116 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个数组 $a$ ，在他看来，如果这个数组满足对于任意的下标 $i$ ，都有 $i \% 2 = a[i] \% 2$ ，那么他对这个数组十分满意。

只不过天不遂人愿，并不是所有的数组都满足这样的条件，但是，牛牛可以通过交换数组中的某些元素使得该数组满足以上情况。

给定一个数组 $a$ ，如果能通过交换数组中的某些元素使得该数组让牛牛十分满意，请返回牛牛需要最少交换的次数，否则，请返回-1。

请注意，数组下标从0开始。

示例1

输入

1,[3]

输出

-1

说明

很显然，3%2 != 0%2，而且无法进行任何的交换，所以返回-1。

示例2

输入

3,[5,4,6]

输出

说明

我们可以交换第一个元素和第二个元素，使得数组变成[4,5,6]，交换后的数组是牛牛满意的，返回最少交换次数1。

备注:

算法知识视频讲解

KevinMcblack

发表于 2020-06-29 21:15:15

这题我们可以思考是否存在一个贪心策略:我们先试着根据题目的意思，统计a[i]%2==1的数量，再统计i%2==1的数量，若两者相等，那么这个数组才有可能使得牛牛满意，反之，返回-1。如果上述条件满足，那么我们发现，我们其实只需要继续统计 i%2 != a[i]%2的数量，最后将这个数量/2就是题目的展开全文