第 26 场 蓝桥入门赛

2.对联【算法赛】 - 蓝桥云课

问题描述

大年三十，小蓝和爷爷一起贴对联。爷爷拿出了两副对联，每副对联都由 N 个“福”字组成，每个“福”字要么是正的（用 1 表示），要么是倒的（用 0 表示）。

爷爷说：“小蓝啊，这两副对联可以随意调整‘福’字的顺序。我们要让上下联的‘福’字对应位置的‘福气值’达到最大。‘福气值’的计算方法是：正正相对得 0，正倒相对得 1，倒正相对得 1，倒倒相对得 0。”

小蓝挠了挠头：“爷爷，这不就是二进制异或运算吗？”

爷爷笑着点点头：“没错！现在给你两串‘福’字的初始排列，你能算出通过最优调整后，最大的总福气值是多少吗？你只需要告诉爷爷最大的总福气值在二进制情况下 1 的个数即可。”

小蓝感觉略微有点困难，于是请你帮忙解决这个问题。

输入格式

第一行输入一个整数 N（1≤N≤1e3），表示每幅对联中“福”的数量。

第二行输入一个长度为 N 的 01 字符串 S 表示第一幅对联的初始排列。

第三行输入一个长度为 N 的 01 字符串 T 表示第二幅对联的初始排列。

输出格式

输出一个整数表示答案。

样例输入

4
0011
1011

样例输出

3

思路：

以最多的0对应最多的1.

代码如下：

#include <iostream>
#include<string> 
using namespace std;
int main()
{
  string s1,s2;
  int n,zero_f = 0,zero_s = 0,one_f = 0,one_s = 0;
  cin >> n >> s1 >> s2;
  for(int i = 0 ; i < s1.size() ; i++)
  {
  	if(s1[i] == '1')
  	zero_f++;
  	if(s1[i] == '0')
  	one_f++;
  }
  for(int i = 0 ; i < s2.size() ; i++)
  {
  		if(s2[i] == '1')
	  	zero_s++;
	  	if(s2[i] == '0')
	  	one_s++;
  }
 // cout << zero_f << " " <<  one_f << endl;
 // cout << zero_s << " " <<  one_s << endl;
  int cnt = 0;
  cnt = min(zero_f,one_s) + min(zero_s,one_f);
  cout << cnt;
  return 0;
}