题解 | 小A弹吉他

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long

void solve() {
    int m;cin >> m;
    int l = 1, r = 2e6;
    int ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (mid * (mid + 1) * (mid + 2) / 6 > m) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

根据排序不等式，数列为1的时候mex为2，数列为1 1 2的时候mex为3，数列为1 1 1 2 2 3的时候mex为4，以此类推，优先分配多的给最小数，当两个序列逆序的时候相乘就是最小值，正序的时候就是最大值，这里考虑最小值，即3*1+2*2+1*3=10，可以推出mex前2到6至少为1,4,10,20,35,可以找出他们的差是有规律的，相当于两个等差数列结合，公式为mid * (mid + 1) * (mid + 2) / 6，二分找最大满足的mid即可，注意上界不要爆ll