• 題意：有 \(n\) 種手套，第 \(i\) 種手套有 \(l_i\) 只左手套和 \(r_i\) 只右手套，現(xiàn)盲抽手套(抽取時無法分辨種類及左右)，至少取多少只手套恰好取 \(k\) 種配對手套？
• 關(guān)鍵詞：貪心(簽到題)
• 題解：
  • 本題需考慮答案的上界(即最壞情況)。
  • 先考慮 \(1\) 種手套。對于無配對情形，通過每次抽取均為同側(cè)即可滿足，上界為 \(\max{(l,r)}\)；對于配對情形，最壞為基于無配對情形的上界，再在另一側(cè)(即 \(\min{(l_i,r_i)}\) 側(cè))取 \(1\) 只手套即可滿足。
  • 再推廣到 \(n\) 種手套。對于 \(k=0\) 時，上界為 \(\sum\limits_{i=1}^n\max{(l_i,r_i)}\)；\(k=1\) 時，基于 \(k=0\) 的上界再在另一側(cè)任取 \(1\) 只即可，而最壞即為任取的手套恰好為剩余手套中最多的那種；\(k=2\) 時，最壞需將 \(k=1\) 時任取的那種手套全部取完，再任取 \(1\) 只即可，上界即 \(\Big(\sum\limits_{i=1}^n\max{(l_i,r_i)}\Big)+\max{(\min{(l_i,r_i)})}+1\)；而 \(k\) 時上界則為將前 \(k-1\) 種全部取完，再任取 \(1\) 只即可。
• 實現(xiàn)：

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
#define int ll
#define endl "\n"

void solve(){
    int n,k;cin>>n>>k;
    vector<int>l(n),r(n),minn(n);
    for(auto &i:l) cin>>i;
    for(auto &i:r) cin>>i;
    int ans=0;
    for(int i=0;i<n;i++){
    	ans+=max(l[i],r[i]);//貪心，先都取最大的那側(cè)
    	minn[i]=min(l[i],r[i]);//剩余沒取的那側(cè)
   	}
    sort(minn.begin(),minn.end(),greater<>());//貪心，每次取沒取的那側(cè)最多的
    for(int i=0;i<k-1;i++) ans+=minn[i];//k-1種全部取完
    cout<<ans+1<<endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int t=1;cin>>t;
    while(t--) solve();
    return 0;
}