题解 | #大佬的生日大礼包#

考察知识点：二分

不难看出每种礼包的构成：「1 个 U 盘 + 1 个鼠标」 + 1 个「U 盘 / 鼠标 / 键盘」 设 U 盘、鼠标、键盘数量为 $a_0,b_0,ca\_0,\; b\_0,\; c$，分配完每个礼包本身含有的 1 个 U 盘和 1 个鼠标后的 U 盘、鼠标数量为 $a,ba,\; b$，礼包数量为 $mm$，则有以下关系式：

• $a=a_0-ma\; =\; a\_0\; -\; m$
• $b=b_0-mb\; =\; b\_0\; -\; m$
• $a,b,c\ge 0a,\; b,\; c\; \backslash geq\; 0$
• $a+b+c\ge ma\; +\; b\; +\; c\; \backslash geq\; m$

由于相邻两位大佬的礼包不能相同，所以还需要满足：

U 盘 / 鼠标 / 键盘中最少的两种物品不少于礼包总数的一半

基于以上判断条件，使用二分查找 $1\sim a+b+c1\; \backslash sim\; a+b+c$ 范围内满足条件的最大礼包数量即可。

时间复杂度：$O(\log (a+b+c))O(\backslash log\; (a+b+c))$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;


bool check(int a, int b, int c, int m)  // a: U盘数量，b: 鼠标数量，c: 键盘数量，m: 礼包数量
{
    a -= m;
    b -= m;
    if (a < 0 || b < 0 || c < 0 || a + b + c < m)
        return false;
    int t[3] = {a, b, c};
    sort(t, t + 3);
    return t[0] + t[1] >= m / 2;        // 相邻的两位礼包不同，要求最少的两种礼包数量之和大于等于礼包总数量的一半
}

void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    int l = 0, r = a + b + c;
    while (l < r)                       // 二分查找礼包数量
    {
        int m = (l + r + 1) >> 1;
        if (check(a, b, c, m))
            l = m;
        else
            r = m - 1;
    }
    cout << l << endl;
}

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