305468: CF1037C. Equalize
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Equalize
题意翻译
给定两个长度为$n$的$01$序列$a,b$ 每次可以执行如下操作: 1. 在$a$中选择一个位置$p$,将$a_p$变为$1-a_p$,代价是$1$ 2. 在$a$中选择两个位置$p,q$,将$a_p$和$a_q$互换,代价是$\mid p-q \mid$ 要求将$a$变成$b$,最小化代价 $1 \le n \le 10^6$题目描述
You are given two binary strings $ a $ and $ b $ of the same length. You can perform the following two operations on the string $ a $ : - Swap any two bits at indices $ i $ and $ j $ respectively ( $ 1 \le i, j \le n $ ), the cost of this operation is $ |i - j| $ , that is, the absolute difference between $ i $ and $ j $ . - Select any arbitrary index $ i $ ( $ 1 \le i \le n $ ) and flip (change $ 0 $ to $ 1 $ or $ 1 $ to $ 0 $ ) the bit at this index. The cost of this operation is $ 1 $ . Find the minimum cost to make the string $ a $ equal to $ b $ . It is not allowed to modify string $ b $ .输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the length of the strings $ a $ and $ b $ . The second and third lines contain strings $ a $ and $ b $ respectively. Both strings $ a $ and $ b $ have length $ n $ and contain only '0' and '1'.
输出格式
Output the minimum cost to make the string $ a $ equal to $ b $ .
输入输出样例
输入样例 #1
3
100
001
输出样例 #1
2
输入样例 #2
4
0101
0011
输出样例 #2
1