题解 P2968 【[USACO09DEC]雪橇Bobsledding】

1124828077ccj · 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;
}