牛客挑战赛53——智乃哥哥的小迷题A

题目链接

思路

在不考虑回退的情况,我们能通过走 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;
} 
上一篇:剑指 Offer 53 - II. 0~n-1中缺失的数字 javascript解法


下一篇:53.最大子序和