1455B Jumps(思维、规律)

﹏ヽ暗。殇╰゛Y 2021-07-17 00:56 323阅读 0赞

B. Jumps  
time limit per test  
1 second  
memory limit per test  
256 megabytes  
input  
standard input  
output  
standard output

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.

思路：先假设一直相加：1+2+3+4+5+6+…+k=sum，  
这时通过观察可以发现假如第一步我选择退后则总和为  
\-1+2+3+4…+k=sum-2,假设在第二步倒退，1-1+3+4+…+k=sum-3，依此类推，我们可以得出我们从一一直加直到>=n(题目的输入),如果刚好=n，答案为k,如果sum-1==n，答案为g+1，我们只有在最后一步倒退可得，步数+1，如果sum>n，答案为g，我们将之前某一步设为到退即可。

Code

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<stack>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e5 + 5;
    int lst[Max];
    int Mod = 1e9 + 7;
    
    int main()
    { 
    	FAST;
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		int i = 0, g = 0;
    		while (i < n)
    		{ 
    			i += (++g);
    		}
    		if (i == n)cout << g << endl;
    		else if (i - 1 == n)cout << g + 1 << endl;
    		else cout << g << endl;
    	}
    }