题目大意

给定一个长度为 nn 的 0101 序列，一共三种操作：

  • 取一只新猫并将其放入盒子中（对于 ii 中的 bi=0b_i = 0，指定 bi=1b_i = 1）。

  • 从盒子中取出一只猫，让它退休（对于 ii 中的 bi=1b_i = 1，指定 bi=0b_i = 0）。

  • 将一只猫从一个盒子移到另一个盒子（对于 i,ji,j 中的 bi=1,bj=0b_i = 1,b_j = 0，指定 bi=0,nj=1b_i = 0,n_j = 1）。

要求用最小的代价将该系列转换为指定序列。

解题思路

十分明显的贪心题，既然每一种操作都是等价的，我们就要让第一种操作和第二种操作的数量尽量减少，所以我们要让第三种情况尽可能多。不难想出以这种方式的话，第一种和第三种操作之和即为两个序列中 11 的个数之差，剩下需要改变的数量即为第三种操作。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Problem: B. Arranging Cats
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

// #define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 2e5 + 9;
const int INF = 0x3f3f3f3f;

char b[N], f[N];

void solve()
{
    int cnt0 = 0, cnt1 = 0, ans = 0;
    int n; cin >> n;
    cin >> b + 1 >> f + 1;
    for (int i = 1; i <= n; i ++)
    {
        if (b[i] == '1') cnt0 ++;
        if (f[i] == '1') cnt1 ++;
        if (b[i] != f[i]) ans ++;
    }
    ans += abs(cnt0 - cnt1);
    cout << ans / 2 << '\n';
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T --) solve();
    return 0;
}