题解 | #小A弹吉他#

集合 ( $\{ t_1, t_2, \dots \}$ ) 必须包含 ( $0, 1, 2, \dots, k-1$ )（每个至少出现一次）。
集合中不能包含 ( k )。

即：存在k个不同的正整数 ( $a_1, a_2, \dots, a_k$ )，它们的出现次数 ( $t_{a_1}, t_{a_2}, \dots, t_{a_k}$ ) 是 ( $\{0, 1, 2, \dots, k-1\}$ ) 的一个排列，并且所有 ( $t_i < k$ )。

为了用最小的 m 实现 mex = k ，让大的出现次数配小的数字值，以最小化序列和。

最优分配方案：数字 i 出现 k-i 次

这样序列和最小值为：

\begin{align*} m(k) &= \sum_{i=1}^{k} i(k-i) \\ &= k \sum_{i=1}^{k} i - \sum_{i=1}^{k} i^2 \\ &= k \cdot \frac{k(k+1)}{2} - \frac{k(k+1)(2k+1)}{6} \\ &= \frac{3k^2(k+1) - k(k+1)(2k+1)}{6} \\ &= \frac{k(k+1)(k-1)}{6} \\ &= \frac{k^3 - k}{6} \end{align*}

要使 mex 至少为 k ，必须满足：

m \ge \frac{k^3 - k}{6}

即：

k^3 - k \le 6m

给定 m ，求最大的整数 k 满足上式。

#include <iostream>
#include<cmath>
using namespace std;

int main() {
    int T;
    cin>>T;
    while(T--){
        long long m,k;
        cin>>m;
        k=pow(6.0*m,1.0/3);
        while(k*k*k-k>6*m)k--;
        while((k+1)*(k+1)*(k+1)-(k+1)<=6*m)k++;
        cout<<k<<endl;
    }
    return 0;
}