題目鏈接
Codeforces Round 99(Rated for Div. 2) – B Jumps
Description
- You are standing on the OX-axis at point 0 and you want to move to an
integer point x>0. You can make several jumps. Suppose you’re
currently at point y (y may be negative) and jump for the k-th time.
You can: either jump to the point y+k or jump to the point y?1. What
is the minimum number of jumps you need to reach the point x?
Input
- The first line contains a single integer t (1≤t≤1000) — the number of
test cases.
The first and only line of each test case contains the single integer x (1≤x≤106) — the destination point.
Output
- For each test case, print the single integer — the minimum number of
jumps to reach x. It can be proved that we can reach any integer
point x.
輸入
5
1
2
3
4
5
輸出
1
3
2
3
4
思路
- 先用+k跳，直到pos=1+2+3+…+k=steps(1+k)/2>=x為止
- 如果pos=x 結束
- 如果pos>x 則把之前的每步逐一換成-1跳，則pos=pos-(step+1)
step∈[1,k],不難發現第k步時pos∈[pos?k?1，pos?2],而pos-k<x 所以當x≠pos-1時必然在第k步時pos范圍內可達到，而x=pos-1時只能加一次-1步，
AC代碼
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int step=0;
while(step*(step+1)/2<n)
step++;
if(step*(step+1)==2*n) cout<<step<<endl;
else{
while(!(n>=step*(step+1)/2-step-1&&n<=step*(step+1)/2-2))
step++;
cout<<step<<endl;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/229821.html
標籤：其他