100%AC题解

第一步：读懂题目并建模
我们有：

n 个灯，每个灯恰好连接 2 个开关。

一共 2n 个开关，每个开关恰好连接 1 个灯（但不知道具体连哪个灯）。

所有开关初始全关时，所有灯也全关。

拨动一个开关会改变它连接的那个灯的状态（亮 ↔ 灭）。

现在给定 2n 个开关的当前状态（0 关，1 开），问：

最少可能有多少个灯是开着的？

最多可能有多少个灯是开着的？

第二步：从“开关状态”到“灯的亮灭”的等价转化
因为每个灯连接两个开关，所以这个灯的亮灭取决于这两个开关的状态：

两个开关状态 相同（都是 0 或都是 1）→ 灯是 灭 的。

两个开关状态 不同（一个 0 一个 1）→ 灯是 亮 的。

为什么？

初始全关时，两个开关都关，灯灭。

后来我们拨动了一些开关（有些开有些关）。如果我们把“拨动”看作翻转一次，灯的最终状态等于两个开关被拨动的总次数的奇偶性。

若两个开关状态相同，则要么都未被拨动（0 次），要么都被拨动（2 次），总次数为偶数 → 灯灭。

若两个开关状态不同，则总拨动次数为奇数 → 灯亮。

所以，问题等价于：

有 2n 个对象，其中 cnt1 个是 1，剩下 2n - cnt1 个是 0。我们要把这些对象分成 n 对（每对对应一个灯），每对如果两个数不同，则这盏灯亮；相同则灭。

我们通过自由分配配对来最大化或最小化“01 配对”的数量。

第三步：最少亮灯数
要让亮灯最少，就要尽量让 同状态 的配成一对。

有 cnt1 个 1， zeros = 2n - cnt1 个 0。

我们可以先把 1 和 1 配对，0 和 0 配对。

当 cnt1 为偶数时，所有 1 能两两配对，所有 0 也能两两配对，这样就没有任何 01 配对，灯全灭，最少 = 0。

当 cnt1 为奇数时，1 的个数是奇数，0 的个数也是奇数（因为总和 2n 是偶数，偶数减奇数 = 奇数）。那么无论怎么配，总会剩下一个 1 和一个 0 无法内部配对，它们必须配对在一起，产生一个亮灯。

所以最少亮灯数 = cnt1 % 2（因为 cnt1 的奇偶性决定了是否有“落单”的）。

第四步：最多亮灯数
要让亮灯最多，就要尽量让 不同状态 的配成一对。

最多的 01 配对数量受限于较少的那个状态的数量。

假设 cnt1 <= zeros，那么最多可以配成 cnt1 对 (1,0)，因为每个 1 可以配一个 0，剩下的 0 两两配对（不产生亮灯）。这样亮灯数就是 cnt1。

若 cnt1 > zeros，那么最多可以配成 zeros 对 (1,0)，剩下的 1 两两配对，亮灯数 = zeros。

综合起来，最多亮灯数 = min(cnt1, zeros)。

第五步：实例验证
例1：n=1，开关 [0, 0]
cnt1=0，zeros=2

最少 = 0%2 = 0，最多 = min(0,2)=0

输出 0 0

例2：[0, 1]
cnt1=1，zeros=1

最少 = 1%2 = 1，最多 = min(1,1)=1

输出 1 1

例3：[1, 1]
cnt1=2，zeros=0

最少 = 0，最多 = min(2,0)=0

输出 0 0

例4：n=3，开关序列 [0,0,1,0,1,0]
统计：cnt1=2，zeros=4

最少 = 2%2 = 0，最多 = min(2,4)=2

输出 0 2

例5：[0,1,1,1,0,0]
cnt1=3，zeros=3

最少 = 3%2 = 1，最多 = min(3,3)=3

输出 1 3

第六步：复杂度分析
只需遍历一次 2n 个开关统计 1 的个数，时间复杂度 O(n)。

空间复杂度 O(1)。

总结
核心思路就是把开关状态看作一堆 0 和 1，任意配对成 n 对，每对不同则灯亮。

最小值 由奇偶性决定（只能靠“落单”产生一个亮灯）。

最大值 由较少数量的状态决定（尽量让 1 和 0 配对）。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while (t--) {
        int n;
        cin>>n;
        int cnt1=0;
        for (int i=0;i<2*n;i++) {
            int x;
            cin>>x;
            cnt1+=x;
        }
        int mn=cnt1 & 1;
        int mx=min(cnt1,2*n-cnt1);
        cout<<mn<<' '<<mx<<'\n';
    }
    return 0;
}