编程题

相同颜色的石头

编程实现:

有两排石头,每排 n 颗,从左到右依次排开,每颗石头的颜色为黄色或者绿色。

每次可以选择第一排的任意一颗石头与第二排的任意一颗石头交换位置。请计算最少需要交换多少次才能让每一列石头的颜色都相同;如果无论交换多少次都无法使每一列石头的颜色都相同,则输出 -1。

例如:n = 3,每排 3 颗石头;

第一排 3 颗石头颜色从左到右依次是黄、绿、绿:

第二排 3 颗石头颜色从左到右依次是绿、绿、黄:

其中一种最少交换次数的方案如下:

(1)先将第一排的第 3 颗石头与第二排的第 3 颗石头交换位置;

(2)再将第一排的第 3 颗石头与第二排的第 1 颗石头交换位置。

此时每一列的石头颜色都相同,故至少需要交换 2 次。

输入描述:

第一行输入一个整数 n(1≤n≤10^5),表示每排的石头数量;

第二行输入 n 个整数,整数只能为 1 或 0,1 表示黄色,0 表示绿色,表示第一排从左到右每颗石头的颜色,整数之间以一个空格隔开;

第三行输入 n 个整数,整数只能为 1 或 0,1 表示黄色,0 表示绿色,表示第二排从左到右每颗石头的颜色,整数之间以一个空格隔开。

输出描述:

输出一个整数,表示最少的交换次数;如果无论交换多少次都无法使每一列的石头颜色都相同,则输出 -1。

 

样例输入:

3
1 0 0
0 0 1

样例输出:

2

查看答案
赣ICP备20007335号-2