题解 | 小A弹吉他

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define endl '\n'
#define int long long
const int N=1e7+1e5;
vector<int> f;
void init(){
    f=vector<int>(N);
    int pref=0;
    for(int i=1;i<N;i++){
        f[i]=f[i-1]+pref+i;
        pref+=i;
    }
}
void solve(){
    int m;cin>>m;
    auto ele=upper_bound(f.begin(),f.end(),m);
    cout<<ele-f.begin()<<endl;
}
signed main(){
    IOS;
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    return 0;
}

可以发现如果我们应该尽量让最大的数出现的次数最小，这样组成的数就能尽可能的大，然后我们发现每个数的出现次数呈现从左往右阶梯状下降，若此时数组的和为 sum 此时只要我们增大最大的数就可以将大于等于sum的m全部取到，因此我们想到二分的判断mex即可，但问题是我们不知道怎么求这个阶梯状数组的和，所以我们可以尝试预处理这个数组，如图