A28691. 有两排石头，每排n颗，从左到右依次排开，每颗石头的颜色为黄色或者绿色。每次可以选择第一排的任意一颗石头与第二排的任意一颗石头交换位置。请计算最少需要交换多少次才能使每一列石头的颜色都相同;如果无论交换多少次都无法使每一列石头的颜色都相同，则输出-1;此时每一列石头的颜色都相同，故至少需要交换2次。
填空题
较难
知识点
题目描述
有两排石头，每排n颗，从左到右依次排开，每颗石头的颜色为黄色或者绿色。每次可以选择第一排的任意一颗石头与第二排的任意一颗石头交换位置。请计算最少需要交换多少次才能使每一列石头的颜色都相同;如果无论交换多少次都无法使每一列石头的颜色都相同，则输出-1;
此时每一列石头的颜色都相同，故至少需要交换2次。
输入格式
本题每个测试点包含多组测试数据第一行包含一个整数 T(1≤T≤300)，表示数据组数接下来T组数据，每组数据第一行输入一个整数n(1≤n≤104) ，表示每排石头的数量
第二行输入 n个整数，整数只能为1或 0，1表示黄色，0 表示绿色，表示第一排从左到右每颗石头的颜色，整数之间以一个空格隔开
第三行输入 n个整数，整数只能为1或0，1表示黄色，0表示绿色，表示第二排从左到右每颗石头的颜色，整数之间以一个空格隔开。
输入样例
2
3
1 0 0
0 0 1
5
1 0 1 0 1
0 1 0 1 0输出样例
2
-1参考答案
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N],b[N],t,n;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]; //读入a
for(int i=1;i<=n;i++)cin>>b[i]; //读入b
int da=0,db=0; //计数器赋值为0
for(int i=1;i<=n;i++)
{
if(a[i]!=b[i])
{
if(a[i])
da++; //计数a需要调整的1的个数
else
db++; //计数b需要调整的1的个数
}
}
if((da+db)%2) //判断能否成功，不成功就输出-1
{
cout<<-1<<endl;
}
else
{
int ans=da/2+db/2; //按照成对进行计算,按照一对1，调整1次来计算。
if(da%2)ans+=2; //有余数，符合调整2次的情况，增加2次。
cout<<ans<<endl; //输出最终结果。
}
}
return 0;
}
上一题
下一题