思路
在不考虑回退的情况，我们能通过走
n
n
n 次到达
1
+
2
+
3
+
.
.
n
1+2+3+..n
1+2+3+..n 的位置。
也就是
1
，
3
，
6
，
10
，
15....
1，3，6，10，15....
1，3，6，10，15.... 这些点
现在假设回退
- 第一次在点0回退，本来要达到点1，回退后相当于- 2
- 第一次在点1回退，本来要达到点3，回退后相当于- 3
- 第一次在点3回退，本来要达到点6，回退后相当于- 4
- 第一次在点6回退，本来要达到点10，回退后相当于- 5
- 第一次在点10回退，本来要达到点15，回退后相当于- 6
通过上面的规律，我们发现。对于 1 ， 3 ， 6 ， 10 ， 15.... 1，3，6，10，15.... 1，3，6，10，15.... 当中的任何点。如果x比其中一个点y 小2及其以上，我们都能在这之前，只通过一次回退操作到达，那么答案就是到达点y的次数。如果小1，那么就到达y点后再回退一次，那么答案就是到达点y的次数+1。
因为数据范围很大，不能用数据存下 1 + . . . + n 1+...+n 1+...+n 的前缀和，所以改用二分答案
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll check(int n){
return 1ll*((1+1ll*n)*n/2);
}
int main(){
int t;
cin>>t;
while(t--){
ll x;
scanf("%lld",&x);
ll l=1,r=1e8,ans;
ll tmpsum=0;
while(l<=r){
ll mid= (l+r)>>1;
if(check(mid)>=x) {
r=mid-1;
ans=mid;
tmpsum=check(mid);
}else l=mid+1;
}
if(x==tmpsum-1) printf("%d\n",ans+1);
else printf("%d\n",ans);
}
return 0;
}