自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:18:31，当前版本为作者最后更新于2025-04-05 17:20:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目便捷入口

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

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

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

1. $(1, 1)$：两排都是 $1$，不需要交换。
2. $(0, 0)$：两排都是 $0$，不需要交换。
3. $(1, 0)$：第一排是 $1$，第二排是 $0$，需要交换。
4. $(0, 1)$：第一排是 $0$，第二排是 $1$，需要交换。

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

• $x$：$(1, 1)$ 的列数。
• $w$：$(0, 0)$ 的列数。
• $y$：$(1, 0)$ 的列数。
• $z$：$(0, 1)$ 的列数。

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

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

第一步：直接配对交换：

• 对于 $(1, 0)$ 和 $(0, 1)$ 的列，可以直接交换这两列的第一排和第二排的石头，这样一次交换可以解决两列的问题。
• 得出来了，我们最少需要 $y \div 2 + z \div 2$ 次交换。

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

• 肯定的的是 $y$ 与 $z$ 都是奇数，我们就会剩下一个 $(1, 0)$ 和一个 $(0, 1)$ 的列。
• 那么为了AC，我们有需要额外两次交换来解决这两列的问题（不得不说很麻烦）：
  • 第一次交换：将 $(1, 0)$ 的第一排 $1$ 与某个 $(1, 1)$ 的第二排 $1$ 交换，得到 $(1, 1)$ 和 $(1, 0)$。
  • 第二次交换：将新的 $(1, 0)$ 的第一排 $1$ 与 $(0, 1)$ 的第二排 $1$ 交换，得到 $(1, 1)$ 和 $(0, 0)$。
• 因此，剩余的两列需要 $2$ 次交换。

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

$$\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。