【二分】爬山

$Link$Link

$SSL\ 1456$SSL 1456

$Description$Description

$Sample$Sample $Input$Input

3 5 2 4

$Sample$Sample $Output$Output

7

$Hint$Hint

$Train$Train $of$of $Thought$Thought

找一个步数，使得它能上升的距离最高且第n步能走到海拔b
那我们就可以二分求这个步数
注意n一开始减一，因为第一步是到达a这个点

$Code$Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long

using namespace std;
int a, b, d;
ll ans, l, r, mid, n;

ll maxx(ll a, ll b)
{
	if (a < b) return b;
	  else return a;
}

bool check(ll x)
{
	ll p = a + x * d;
	if (p < b) {
		ans = maxx(ans, p);
		return 1;
	} 
	if (d * (n - x) < (p - b)) {
		for (int i = d - 1; i >= 0; --i) { 
			ll q = a + (x - 1) * d + i;
			if (d * (n - x) >= (q - b)) {
				ans = max(q, ans);
				return 1;
			}
		} 
		return 0;
	} 
	ans = maxx(ans, p);
	return 1; 
}

int main()
{
	scanf("%lld%d%d%d", &n, &d, &a, &b);
	n -= 1;
	l = 0; r = n; 
	while (l <= r)
	{
		mid = (ll)((l + r) / 2);
		if (check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	printf("%lld", ans);
	return 0;
}