CF1455B

发表于 | 分类于 |

题面：第k次动作可以为向前走k步或向后退1步，给定坐标x，求最少需要几步才能走到x

正解:假设走k次，若k次全向前，则走了步，若k-1次向前时，当前位置在x前面，则k-1次必定到不了x，故我们找到最小的k满足

我们进行分类讨论，能否在第k步到达x

1.若当前位置等于x，则第k步即为最优答案

2.若当前位置大于x，我们能否通过将一定数量的前进改成后退来使当前位置等于x？将第k次向前改成向后，可以视作向后走k+1步，但修改一定数量太难考虑，故我们想进一步缩小范围，证明修改两步以上是冗余的做法，可以通过修改1步做到

证明如下：若需要后退的步数大于k，则与第k-1次前进没到达x的假设相悖;若需要后退的步数小于k，则后退2~k+1步都能通过修改一次前进得到；若需要后退的步数等于1，则修改一次无法达到效果，必须多一次后退操作

附code：

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
40
41
42
43
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m, k;
ll a[200005];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> T;
	while (T--)
	{
		cin >> n;
		ll tmp = 0;
		while (tmp * (tmp + 1) / 2 < n)
		{
			tmp++;
		}
		if (n + 1 == tmp * (tmp + 1) / 2)
		{
			cout << tmp + 1 << '\n';
		}
		else
		{
			cout << tmp << '\n';
		}
	}	
	return 0;
}