核心问题与数学模型

本题要求我们构造一个和为 的正整数序列 ，使得序列中各元素出现次数集合 的 值（最小未出现的非负整数）最大化。

1. MEX 的约束

要使 ，要求该集合必须包含所有小于 的非负整数：。由于序列长度有限，总有未使用的数字 使得 成立，因此 总是存在。我们实际需要确保序列的出现频次中包含所有正整数 。

2. 贪心构造与最小代价

为了使目标 值 尽可能大，我们需要用最小的总和来构造所需的频次。

我们令 为所需凑出的连续频次数量，即 。我们需要构造 种不同的正整数 ，它们的出现次数恰好是 的一个排列。

根据贪心策略（排序不等式），为使总和 最小，我们必须将最大的频次分配给最小的数值。因此，最小代价 由 种数值 和 种频次 交叉乘积的最小和构成：

计算这个和，得到四面体数公式：

求解算法

该问题转化为：找到满足 的最大整数 。

由于 的范围高达 ，而 ，其最大值约为 ，因此我们可以使用二分查找高效求解。

方法一：以频次数量 为目标 (对应 )

  1. 二分查找目标：在 范围内，查找最大的整数 ，使得：
  2. 最终结果：最大的 值 为 。

方法二：以 MEX 值 为目标 (对应 )

  1. 二分查找目标：令 为目标 值。我们需要 。将 代入 公式，查找最大的 ，使得：
    化简后即为：
  2. 最终结果：最大的 值即为 。

这两种方法是完全等价的，都基于相同的最小代价公式，仅变量定义不同。我们通常选择方法二，因为它直接求解最终答案 。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        ll m;
        cin >> m;

        auto check = [&](ll k) -> bool {
            return (k - 1) * k * (k + 1) <= 6 * m;
        };

        ll low = 1;
        ll high = 2 * 1e6;
        ll ans;
        while (low <= high) {
            ll mid = low + (high - low) / 2;
            if (check(mid)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        cout << high << '\n';
    }
}

复杂度分析

对于 组测试数据，我们对 （或 ）进行二分查找。由于 ，二分查找的复杂度为 。总时间复杂度为 ，在本题中效率极高。