抽屉原理

定义

抽屉原理，亦称鸽巢原理（The Pigeonhole Principle）。

它常被用于证明存在性证明和求最坏情况下的解。

简单情况

将 $n+1$ 个物体，划分为 $n$ 组，那么有至少一组有两个（或以上）的物体。

这个定理看起来比较显然，证明方法考虑反证法：假如每个分组有至多 $1$ 个物体，那么最多有 $1\times n$ 个物体，而实际上有 $n+1$ 个物体，矛盾。

实际解释

对于需要配对的物品 $ n $ ，我们可以根据需要把它分为多个盒子（考虑最坏情况下的盒子数目），先按照条件向盒子中添加上需要配对的物品之一，然后对于剩下的物品，我们考虑最坏条件下需要拿到几个东西才能装满一个盒子，又有多少个盒子装不满。

例题

B. Wonderful Gloves - Codeforces

题解

对于一种颜色的手套，我们最多有可能配对出$mx_i = max(Left[i],Right[i])$组手套，即我们开了$mx_i$个盒子，每个盒子先放入一只左或者右手套，然后对于每种颜色的盒子，我们最多能向$mi_i = min(Left[i],Right[i])$个盒子中放入缺少的另一个（即配对）。考虑到最坏的情况，即一开始每次拿出的手套每个都是不配对的，那最多拿到$\sum_{i=0}^nmx_i$个能是单的，考虑配对的时候，最坏情况是前$k-1$种颜色的单个手套被尽可能的全部被配对（即先降序排序$mi_i$，然后拿出前$k-1$个数列元素），对于最后一种颜色$k$，我们无论再拿出什么颜色的手套，此时一定能配对一个，则配对了$k$种颜色的手套，每个颜色至少拿一个的最坏情况（即答案）。

C++实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e6 + 10; //100005


int l[N],r[N],a[N];
void solve()
{
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> l[i];
    for(int i=1;i<=n;i++) cin >> r[i];
    int ans = 0;
    for(int i=1;i<=n;i++) ans += max(l[i],r[i]),a[i] = min(l[i],r[i]);
    sort(a+1,a+1+n,greater<>());
    for(int i=1;i<=k-1;i++) ans += a[i];
    cout << ans + 1 << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int _ = 1;
    cin >> _ ;
    while(_--)
    {
        solve();
    }
    return 0;
}