题解 | #智乃哥哥的小迷题A#
智乃哥哥的小迷题A
https://ac.nowcoder.com/acm/contest/11193/A
题目大意
初始你在坐标轴的0处，你要走到n处
第x步你可以进行以下操作：
- 向右走x步
- 向左走一步
解题思路
先尽量往右走，直到再走一步会超过n，这个过程可以二分处理
设现在走了l步，那么可以在任意一步的前面往左走一步，这样会使后面的步数都+1,那么会造成-1~l-1步的贡献（往左走了一步，所以要减一）
又因为n-l<l+1，如果n-l<l那么答案+1，否则答案+2（往右走一步再往左走一步）
code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll T,x,l,r,mid;
ll get(ll x)
{
return x*(x+1)/2;
}
int main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld",&x);
l=0;
r=1e8;
while(l<r){
mid=l+r+1>>1;
if(get(mid)>=x)r=mid-1;
else l=mid;
}
if(x-get(l)==l)printf("%lld\n",l+2);
else printf("%lld\n",l+1);
}
return 0;
}
查看1道真题和解析
网易游戏公司福利 634人发布