题目要求: 的最大 值。

思路解析：

比方说 时，最小和为

  • 可以发现上述两个式子是等价的，当 的时候就在这个前提再加上 。这样的话我们提前预处理一下，最后结果再二分查找即可。

预处理阶段：

计算对于每个 ，和式的值是如何累积的。

这种结构的累加和可以通过递推方式计算。即每增加一个 ，就加上从 1 到 的和。例如：

  • 当 时，最小值为
  • 当 时，最小值为
  • 当 时，最小值为
  • 当 时，最小值为

二分查找：

直接查表二分即可.

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>ans;
void solve() {
    int x;
    cin >> x;
    int mark = 0;
    mark = upper_bound(ans.begin() + 1, ans.end(), x) - ans.begin() - 1;
    cout << mark + 1 << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ans.resize(1817120 + 5);
    for (int i = 1; i <= 1817120; i++) {
        ans[i] = i * (i + 1) / 2 + ans[i - 1];
    }
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello, World!"); 
    }
}

print('Hello world!')