网站联系我们模板马连洼网站建设

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;
}