题解 | #小A弹吉他#

思路

这题我们不难发现，要使得最终的mex尽可能的大，需要我们使用一个贪心策略，假设最终的mex为x+1，那么我们需要构造一个式子, ,要使得式子的求和尽量的少，我们只需要令 即可，那么最终的求和就是 个平方推导之后的结果就是 ,然后接下来就是二分答案的事情。

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m;
bool check(ll mid)
{
    ll res= (mid+1)*mid*(mid+2)/6;
    return res<=m;
}

void solve()
{

    cin>>m;
    ll l =1,r=2e6;
    ll res=1;
    while(l<=r)
    {
        ll mid = (l+r)>>1;
        if(check(mid))
        {
            res = mid;
            l = mid+1;
        }
        else 
        {
            r = mid-1;
        }
    }
    res++;
    cout<<res<<endl;

}

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}