CF1455B-Jumps

2020-12-15 约 442 字预计阅读 1 分钟次阅读

CF1455B-Jumps

题目:

题目描述:

You are standing on the $ \mathit{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 $ ?

输入格式:

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases.

The first and only line of each test case contains the single integer $ x $ ( $ 1 \le x \le 10^6 $ ) — the destination point.

输出格式:

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:

样例输出1:

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Problem: CF1455B Jumps
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1455B
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
typedef long long ll;
const int maxn = 1000005;
int TTT;
int x, k, ans;
int s[10005];
int main()
{
    yin >> TTT;
    for (int i = 1; i < 10005 && (1 + k) * k / 2 < maxn; i++)
        s[i] = s[i - 1] + i;
    while (TTT--)
    {
        ans = 999999999;
        yin >> x;
        int a = lower_bound(s + 1, s + 1 + 10005, x) - s;
        int b = s[a] - x;
        if (b == 0)
            ans = a;
        if (b != 0)
        {
            int k = b - 1;
            if (k != 0)
                ans = min(ans, a);
            else if (k == 0)
                ans = min(ans, a + 1);
        }
        yout << ans << endl;
    }
    return 0;
}

目录

CF1455B-Jumps

CF1455B-Jumps

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入1:

样例输出1:

思路:

实现: