题解：B4307 [蓝桥杯青少年组国赛 2024] 第二题

· · 题解

题目便捷入口

看题目，题目说我们有两排石头，每个石头不是黄色就是绿色；

让我们第一排某个位置和第二排的某个位置交换，或者就是第二排的某个位置和第一排交换，也就是说不可能是第 x 行的某个位置和第 x 行的某个位置交换！

从此，我们可以将每一列的颜色组合分为以下四种情况：

然后……我们假设这四个情况的列数分别为：

从此，我想出了一个不可能实现结果的结论： 如果 y + z 是奇数，直接返回 -1。

OK，那么第一时间搞定了可不可能的问题，接下来，我们就要开始看看要多少次（最少）完成任务了。

第一步：直接配对交换：

第二步： 剩余未配对的列：

最终，我们辛辛苦苦干出来的公式：

\left\lfloor \frac{y}{2} \right\rfloor + \left\lfloor \frac{z}{2} \right\rfloor + (y \bmod 2) \times 2

上代码了：

#include <bits/stdc++.h>  // 好习惯*1
using namespace std;

int main() {
    int T;  // 测试数据组数
    cin >> T;
    while (T--) {  
        int n;  
        cin >> n;
        int a[10005], b[10005];  //石头石头来了

        // 第一排石头
        for (int i = 0; i < n; ++i)
             cin >> a[i];
        // 第二排石头
        for (int i = 0; i < n; ++i)
             cin >> b[i];
        int x = 0;  // 两排都是1的列数
        int y = 0;  // 第一排1第二排0的列数
        int z = 0;  // 第一排0第二排1的列数
        int w = 0;  // 两排都是0的列数
        for (int i = 0; i < n; ++i) {
            if (a[i] == 1 && b[i] == 1) x++;
            else if (a[i] == 1 && b[i] == 0) y++;
            else if (a[i] == 0 && b[i] == 1) z++;
            else w++;
        }
        // 如果需要交换的列数(y+z)是奇数，则无解
        if ((y + z) % 2 != 0) {
            cout << -1 << '\n';
            continue;  // 跳过本次循环，处理下一组数据
        }
        // 计算最少交换次数：
        // 1. 每对(1,0)和(0,1)可以直接交换解决，需要y/2 + z/2次
        // 2. 如果y和z是奇数，最后会剩下一对(1,0)和(0,1)，需要额外2次交换
        int ans = y / 2 + z / 2 + (y % 2) * 2;
        cout << ans << '\n';  // 输出结果
    }
    return 0;  //好习惯*2
    为了您的安全，请不要抄袭代码！！！这非常重要！
}

真心希望大家可以学会这道题，掌握知识点和如何推导公式qwq。