题解 | 小A弹吉他

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
constexpr int MOD = 1e6 + 3, INF = 2e6;
mt19937_64 rg(random_device{}());
int rnd(int l, int r)
{
    return l + rg() % (r - l + 1);
}
void solve()
{
    int m;
    cin >> m;
    auto check = [&](int x)
    {
        int cal = (x * (x + 1) / 2) * (x + 2) / 3;
        return cal <= m;
    };
    int l = 0, r = INF, ans = l;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans + 1 << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testcase = 1;
    cin >> testcase;
    while (testcase--)
    {
        solve();
    }
    return 0;
}

首先，在本题中最优的策略让mex = x一定是集合中有0,1,2,3,4...x-1，我们发现因为数量很多，一定有0，我们只需要考虑分配m为若干个数，我们在注意到，假如集合是1-x，最小分配策略是1有x个，2有x-1个... x有1个 ，所需要的m>= x*(x + 1)*(x + 2) / 6,(这个式子可以自己推导一下)，然后就是显然的二分一下答案就行了