题解 | #小A弹吉他
小A弹吉他
https://www.nowcoder.com/practice/1ea8f581cc1a4db9b098faf82a7b0850
题目要求: %20%5Cle%20x&preview=true)
的最大 
值。
思路解析：
比方说 时，最小和为
- 可以发现上述两个式子是等价的，当
的时候就在这个前提再加上
。这样的话我们提前预处理一下，最后结果再二分查找即可。
预处理阶段：
计算对于每个 ，和式的值是如何累积的。
这种结构的累加和可以通过递推方式计算。即每增加一个 ，就加上从 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!')