本文共 1156 字，大约阅读时间需要 3 分钟。

题目

题意

有一个点在第1分钟位于$a$这个位置
从第2~$n$分钟可以向上或向下走最多$d$的高度
要求在第$n$分钟结束后到达$b$这个位置，求能到达的最高高度

分析

先考虑$O(n)$
设当前高度为$x$
很显然对于一个$i(2\le i\le n)$，如果是合法的，满足$x+d-d\ast (n-i)\le b$
如果成立，答案和$x+d$取$max$
如果不成立，那么最高高度只能是$b+d\ast (n-i)$，和答案取$max$
但是看到$n$是小于等于10¹²的，$O(n)$是过不去的，考虑优化
我们可以二分求出最大的$i$使得$a+d\ast (i-1)-d\ast (n-i)\le b$成立，这样的话时间就是$O(log(n))$

Code

#include<cstdio>#include<iostream>using namespace std;long long i,n,d,a,b,l,r,mid,ans;int main(){       freopen("mountain.in","r",stdin);    freopen("mountain.out","w",stdout);    scanf("%lld%lld%lld%lld",&n,&d,&a,&b);    l=2;    r=n;    while (l<=r)    {           mid=(l+r)>>1;        if (a+d*(mid-1)-d*(n-mid)<=b)        {               l=mid+1;            ans=max(ans,a+d*(mid-1));        }        else         {               r=mid-1;            ans=max(ans,b+d*(n-mid));        }    }    printf("%lld\n",ans);    fclose(stdin);    fclose(stdout);    return 0;}