一、题目大意回顾

有 $n$ 种颜色的手套，每种颜色 $i$ 有 $l_i$ 只左手手套、$r_i$ 只右手手套。 在完全看不见手套的前提下，随机从抽屉抽取手套。 一副合法配对定义为：同一种颜色 1 只左手 + 1 只右手。 要求求出最少抽取多少只手套，能保证一定存在至少 $k$ 副不同颜色的配对。

本质是最坏情况构造 + 贪心极值问题： 我们先构造「最多能抽多少只，仍然凑不出 $k$ 种不同配对」，答案就是这个数量 $+1$。

二、核心解题思想

本题采用逆向贪心思维： 不去直接求保证 $k$ 对的最小数量， 而是先求最坏情况下，最多能拿多少只手套，最多只有 $k-1$ 种不同颜色配对， 再在此基础上加 1，就是题目要求的答案。

设 $m = k-1$，代表允许最多存在 $m$ 种不同颜色配对，我们构造极限最多手套数 $y$，最终答案 $ans = y+1$。

三、贪心策略逐层推导

1. 基础定义

对每种颜色 $i$：

• $a_i = \max(l_i, r_i)$：只拿单种手势（全左或全右）能拿的最大数量，此时完全无法形成任何配对；
• $b_i = \min(l_i, r_i)$：剩下另一种手势的手套数量，这部分是后续可以补出来形成配对的余量。

2. 当 $m=0$（不能有任何一对配对）

想要一只配对都凑不出来，最优最坏策略： 每种颜色只拿数量多的那一手，全部累加：

此时所有手套都是单左手或单右手，没有任何一副完整配对。

3. 当 $m=1$（最多只能有 1 种颜色配对）

在 $m=0$ 的基础上，我们可以额外多选一种颜色的全部余量 $b_i$，让这一种颜色可以形成配对，其余颜色仍无配对。 为了让总手套数最大，贪心选择**$b_i$ 最大**的那一个值加上去：

4. 当 $m=2$（最多只能有 2 种颜色配对）

同理，在基础总和上，加上最大的两个 $b_i$：

5. 推广到一般 $m=k-1$

想要最多只存在 $k-1$ 种不同颜色配对：

1. 先累加所有颜色的 $a_i$；
2. 将所有 $b_i$ 从大到小排序；
3. 取前 $k-1$ 个最大的 $b_i$ 累加到总和；
4. 此时得到的 $y$ 就是最坏情况下不满足要求的最大手套数；
5. 答案即为 $y+1$。

四、正式算法步骤

1. 多组测试用例输入，依次处理每组数据；
2. 读入颜色数 $n$、要求配对种数 $k$，令 $m = k-1$；
3. 读入左手数组 $l$、右手数组 $r$；
4. 遍历每种颜色，计算 $a_i=\max(l_i,r_i),\ b_i=\min(l_i,r_i)$，累加所有 $a_i$ 得到基础和；
5. 将 $b$ 数组降序排序；
6. 累加前 $m$ 个最大的 $b_i$ 到总和；
7. 最终答案为总和 $+1$，输出即可。

五、标准程序代码

#include <bits/stdc++.h>
using namespace std;

void test() {
    int n, k;
    cin >> n >> k;
    int m = k - 1;

    vector<int> l(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    vector<int> r(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }

    vector<int> a(n), b(n);
    long long y = 0;
    for (int i = 0; i < n; i++) {
        a[i] = max(l[i], r[i]);
        b[i] = min(l[i], r[i]);
        y += a[i];
    }

    sort(b.begin(), b.end(), greater<>());
    for (int i = 0; i < m; i++) {
        y += b[i];
    }

    long long x = y + 1;
    cout << x << '\n';
}

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

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
    
    return 0;
}