题解

思路分析

这是一道 状态枚举 + 贪心 的组合优化问题。

问题建模

• 两个抽屉分别有 $n$ 种颜色的左/右手套，数量为 $a_i$ 和 $b_i$
• 需要确保至少拿到一副同色手套（一只左手一只右手）
• 求最少需要拿多少手套

核心思路

1. 关键观察

要保证至少有一副同色手套，有两种极端策略：

• 策略A：拿完所有左手套 + 一些右手套（确保至少有一种颜色配对）
• 策略B：拿完所有右手套 + 一些左手套（确保至少有一种颜色配对）

实际上，我们可以在两个抽屉中各取一部分。

2. 枚举子集

由于 $n \leq 20$，可以枚举 $2^n$ 种取法（每种颜色是否完全取完某一侧）。

对于一个子集 $mask$：

• 如果 $mask$ 的第 $i$ 位为 1：取完所有左手的第 $i$ 种颜色手套
• 如果 $mask$ 的第 $i$ 位为 0：考虑从右手取第 $i$ 种颜色

3. 贪心计算

对于确定的左手取法，右手应该怎么取？

设左手取了集合 $S$ 的所有手套，右手取了集合 $T$ 的一些手套：

• 如果某种颜色 $i \in S$（左手全取），右手至少取 $1$ 只（否则无法配对）
• 如果某种颜色 $i \notin S$（左手不全取），右手必须全取（确保其他颜色能配对）

4. 优化技巧

• 预处理零值：如果 $a_i = 0$ 或 $b_i = 0$，这种颜色无法配对，直接计入答案
• 枚举优化：对于左手全取的集合，右手的取法是确定的（贪心）

算法步骤

1. 预处理：

   • 去除无法配对的颜色（$a_i = 0$ 或 $b_i = 0$）
   • 累加它们的数量作为基础答案

2. 枚举左手子集 $mask$ ($0$ 到 $2^n - 1$)：

   • 计算左手总数：$\sum_{i \in mask} a_i$
   • 计算右手总数：$\sum_{i \notin mask} b_i$（全取）+ $\sum_{i \in mask} 1$（各取一只）
   • 如果左/右手总和不等于总和，需要额外加1（确保配对）
   • 更新最小值

3. 输出答案

复杂度分析

• 时间复杂度：$O(2^n \cdot n)$
• 空间复杂度：$O(n)$

由于 $n \leq 20$，$2^{20} \approx 10^6$ 可以接受。

/*
    Trần Duy Vũ - THPT Chuyên Lương Thế Vinh
*/
#include<bits/stdc++.h>
using namespace std;
using namespace chrono;
using ll = long long;

template <class X, class Y>
void ckmin(X &x, const Y &y) { if (x > y) x = y;}
template <class X, class Y>
void ckmax(X &x, const Y &y) { if (x < y) x = y;}

#define Duy_vu_dep_trai int main
Duy_vu_dep_trai() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<int> a(n), b(n);
    for (int i= 0; i< n; i++) {
        cin >> a[i];
    }
    for (int i= 0; i< n; i++) {
        cin >> b[i];
    }
    int Sum_a= 0, Sum_b= 0, rebu_a= 0, rebu_b= 0;
    for (int i= 0; i< n; i++) {
        if(!a[i] || !b[i]) {
            rebu_a+= a[i];
            rebu_b+= b[i];
            swap(a[i], a[n - 1]);
            swap(b[i], b[n - 1]);
            n --;
            i--;
        }
        else {
            Sum_a+= a[i];
            Sum_b+= b[i];
        }
    }
    a.resize(n);
    b.resize(n);
    vector<pair<ll, ll>> pairs;
    for (int m1= 0; m1 < (1<< n); m1++) {
        int lef= 0, rig= 0;
        for(int i= 0; i< n; i++) {
            if(m1>>i & 1) {
                lef+= a[i];
            }
            else {
                rig+= b[i];
            }
        }
        pairs.push_back(make_pair(lef, rig));
    }
    sort(pairs.begin(), pairs.end());
    reverse(pairs.begin(), pairs.end());
    int ma= 0, Answers_a=1e9, Answers_b=1e9;
    for (int i= 0; i< pairs.size(); i++) {
        int x=pairs[i].first, y=pairs[i].second;
        if(x+ (x!= Sum_a) + ma + (ma!= Sum_b) < Answers_a+ Answers_b) {
            Answers_a= x+ (x!= Sum_a);
            Answers_b= ma + (ma!= Sum_b);
        }
        ckmax(ma, y);
    }
    cout<<Answers_a+rebu_a <<"\n" <<Answers_b+rebu_b <<endl;
}

题解

核心思路是把“左右抽屉中存在某个颜色的手套同时被取走”转化为 Pigeonhole 思维。若某个颜色只在一侧出现（另一侧数量为 0），那一侧的所有手套都必须拿走，否则永远不可能凑成这一颜色的配对——代码用 rebu_a/rebu_b 事先统计这些必取数量，并把对应颜色剔除。

对剩余颜色，假设我们决定取走其中一部分颜色的所有左手手套，并把其它颜色交给右手抽屉负责。若我们从左边取走集合 $S$ 的全部手套，那么只要右边保证至少有一个颜色来自 $S$，就能配对；若 $S$ 并非全部颜色，还需要在左边额外多拿 1 只手套以跨过抽屉边界的“安全线”。右边也有完全对称的考虑：若右侧负责集合 $T$ 的全部颜色，当 $T$ 不是全集时，也要再加 1。

因此可以枚举剩余颜色的所有划分。程序把每个子集对应的“左侧总数 lef”与“其余颜色右侧总数 rig”记录下来，按 lef 递减排序，并用扫描的方式维护当前遇到的最大 rig。对每个候选子集 $S$（记录为 lef）与之前扫描到的最佳对向集合（记录为 ma），尝试更新答案：左边需取 lef + (lef != Sum_a)，右边需取 ma + (ma != Sum_b)。二者之和即当下策略的总手套数。

历遍所有子集即可得到最小的左右抽屉取值，再把之前剔除的必取手套加回去就是最终答案。由于有效颜色最多 20 种，暴力子集的复杂度为 $O(2^n n)$，完全可行。

/*
    Trần Duy Vũ - THPT Chuyên Lương Thế Vinh
*/
#include<bits/stdc++.h>
using namespace std;
using namespace chrono;
using ll = long long;

template <class X, class Y>
void ckmin(X &x, const Y &y) { if (x > y) x = y;}
template <class X, class Y>
void ckmax(X &x, const Y &y) { if (x < y) x = y;}

#define Duy_vu_dep_trai int main
Duy_vu_dep_trai() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<int> a(n), b(n);
    for (int i= 0; i< n; i++) {
        cin >> a[i];
    }
    for (int i= 0; i< n; i++) {
        cin >> b[i];
    }
    int Sum_a= 0, Sum_b= 0, rebu_a= 0, rebu_b= 0;
    for (int i= 0; i< n; i++) {
        if(!a[i] || !b[i]) {
            rebu_a+= a[i];
            rebu_b+= b[i];
            swap(a[i], a[n - 1]);
            swap(b[i], b[n - 1]);
            n --;
            i--;
        }
        else {
            Sum_a+= a[i];
            Sum_b+= b[i];
        }
    }
    a.resize(n);
    b.resize(n);
    vector<pair<ll, ll>> pairs;
    for (int m1= 0; m1 < (1<< n); m1++) {
        int lef= 0, rig= 0;
        for(int i= 0; i< n; i++) {
            if(m1>>i & 1) {
                lef+= a[i];
            }
            else {
                rig+= b[i];
            }
        }
        pairs.push_back(make_pair(lef, rig));
    }
    sort(pairs.begin(), pairs.end());
    reverse(pairs.begin(), pairs.end());
    int ma= 0, Answers_a=1e9, Answers_b=1e9;
    for (int i= 0; i< pairs.size(); i++) {
        int x=pairs[i].first, y=pairs[i].second;
        if(x+ (x!= Sum_a) + ma + (ma!= Sum_b) < Answers_a+ Answers_b) {
            Answers_a= x+ (x!= Sum_a);
            Answers_b= ma + (ma!= Sum_b);
        }
        ckmax(ma, y);
    }
    cout<<Answers_a+rebu_a <<"\n" <<Answers_b+rebu_b <<endl;
}