# B. Wonderful Gloves [문제 링크](https://codeforces.com/contest/2096/problem/B) ## Problem Statement You are the proud owner of many colorful gloves, and you keep them in a drawer. Each glove is in one of $n$ colors numbered $1$ to $n$. Specifically, for each $i$ from $1$ to $n$, you have $l_i$ left gloves and $r_i$ right gloves with color $i$. Unfortunately, it's late at night, so **you can't see any of your gloves**. In other words, you will only know the color and the type (left or right) of a glove **after** you take it out of the drawer. A matching pair of gloves with color $i$ consists of exactly one left glove and one right glove with color $i$. Find the minimum number of gloves you need to take out of the drawer to **guarantee** that you have **at least** $k$ matching pairs of gloves with **different** colors. Formally, find the smallest positive integer $x$ such that: - For any set of $x$ gloves you take out of the drawer, there will always be at least $k$ matching pairs of gloves with different colors. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains two integers $n$, $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of different colors, and the minimum number of required matching pairs of gloves. The second line of each test case contains $n$ integers $l_1, l_2, \ldots, l_n$ ($1 \le l_i \le 10^9$) — the number of left gloves with color $i$ for each $i$ from $1$ to $n$. The third line of each test case contains $n$ integers $r_1, r_2, \ldots, r_n$ ($1 \le r_i \le 10^9$) — the number of right gloves with color $i$ for each $i$ from $1$ to $n$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output a single integer — the minimum number of gloves you need to take out of the drawer. ## 풀이 #### a_i, b_i 둘 다 얻는 것이 k개가 되야 한다. a와 b중에 큰 것 먼저 전부 선택하고, 남은 것 중에서 큰 k-1개를 선택하고 +1 해주면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int l[200000], r[200000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n, k; cin >> n >> k; long long res=0; priority_queue<int> pq; for(int i=0;i<n;i++) cin >> l[i]; for(int i=0;i<n;i++) cin >> r[i]; for(int i=0;i<n;i++) { res += max(l[i], r[i]); pq.push(min(l[i], r[i])); } while(k-->1) { res += pq.top(); pq.pop(); } cout << res+1 << '\n'; } } ```