自动搬运

查看原文

来自洛谷，原作者为

	1124828077ccj **

搬运于2025-08-24 21:43:56，当前版本为作者最后更新于2017-01-31 13:51:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题初看有些无从下手。不过我们可以从后往前推出：对于每个拐角，经过它的速度的最大限制（既要小于题目给出的安全限制，又要确保后面的拐角能够顺利通过）。

知道这个之后，我们就可以从前往后模拟，计算出每两个拐角之间的速度最大值（不要忘了还有起点和终点），以及到达拐角时的速度。

到达拐角时的速度应该比较容易推，速度最大值要用点脑子（请参考代码）

附代码（并不会很长）

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
int l,n,ans,m;//m表示到达某个拐角时的速度
typedef struct{
    int t,s,q;
}P;
bool cmp(P aa,P bb){
    return (aa.t<bb.t);
}
P p[100002];
int main()
{
    scanf("%d%d",&l,&n);
    for (int i=1;i<=n;i++)
    scanf("%d%d",&p[i].t,&p[i].s);
    sort(p+1,p+n+1,cmp);p[n].q=p[n].s;//切记要排序
    for (int i=n;i>=2;i--)
    p[i-1].q=min(p[i-1].s,p[i].q+p[i].t-p[i-1].t);//推出最大速度限制
    if (p[1].t+1<=p[1].q)ans=p[1].t+1;
    else ans=(p[1].q+p[1].t+1)/2;
    m=min(p[1].q,p[1].t+1);//起点与第一个拐角的信息
    for (int i=2;i<=n;i++)
    {
        if (m+p[i].t-p[i-1].t<=p[i].q) ans=max(ans,m+p[i].t-p[i-1].t);
        else ans=max(ans,(p[i].q+p[i].t-p[i-1].t+m)/2);
        m=min(p[i].q,m+p[i].t-p[i-1].t);//i和i-1个拐角的信息
    }
    printf("%d",max(ans,m+l-p[n].t));//不要忘了终点
    return 0;
}