【2018.1.30普及组模拟】溜冰 //2018.1.30

题目

题目描述
Smart迷上了溜冰，并准备参加国际溜冰比赛。国际溜冰比赛的赛道长L米。Smart在起点的速度是1米/秒，但他的速度是可以改变的，在每一米的速度可以是前一米的速度加1、减1，或者等于前一米的速度。在滑行的过程中，Smart会遇到N个转弯处，第i个转弯处位于距离出发点D[i]米处。为了安全，Samrt到达第i个转弯处的速度不能超过S[i]米/秒。Smart到达终点时的速度没有最大限制。请你帮忙计算Samrt溜冰过程中最大的速度是多少？
下面的例子，距开始7米处限速为3、11米处限速为1、13米处限速为8，如下图：

输入
第一行两个整数L和N。
第二行到第N+1行：第i+1行表示第i个转弯处的两个参数D[i]，S[i]。
输出
输出仅一行，一个整数表示滑行过程中的最大速度（包括起点和终点的速度）。
数据范围限制
30%的数据：2≤L, N≤100；
50%的数据：2≤L, N≤1000；
100%的数据：2≤L≤10^9，1≤N≤10^5，1≤D[i]≤L-1，1≤S[i]≤10^9。

---

解题思路

贪心，模拟。分四种情况t[i].d,t[i+1].d：1.整个过程一直加速【t[i].s=t[i-1].s+D; maxn=max(maxn,t[i].s); 】2.当前转弯处的限速大于前一个转弯处限速,先加速再减速，【maxn=max(maxn,(t[i].s+t[i-1].s+D)/2);】3.当前转弯处的限速小于前一个转弯处限速,先加速再减速【maxn=max(maxn,(t[i].s+t[i-1].s+D)/2);】4.无论如何减速，都无法t[i].s都无法变成t[i+1].s;

先预先处理(4)情况（n->1），再处理前三种情况

---

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std; 
struct node{
    int d,s; 
}t[100010];
int l,n,maxn; 

bool cmp (node x,node y)
{ return x.d<y.d;  }//结构体排序

int main()
{
    //freopen("skate.in","r",stdin); 
    //freopen("skate.out","w",stdout); 
    scanf("%d%d",&l,&n); 
    for (int i=1;i<=n;i++)
     scanf("%d%d",&t[i].d,&t[i].s);//.d记录位置，.s记录最大限制
    sort(t+1,t+n+1,cmp); //快速排序
    t[0].d=0; t[0].s=1; t[n+1].d=l; t[n+1].s=l+1; //把起点与终点都想象成转弯处
    for (int i=n;i>=1;i--)
    {
      int D=t[i].d-t[i-1].d; 
      if (t[i].s<t[i-1].s) t[i-1].s=min(t[i-1].s,t[i].s+D);     //处理第四种情况
    }
    for (int i=1;i<=n+1;i++)
     {
        int D=t[i].d-t[i-1].d; 
        if (t[i].s>t[i-1].s)
         {
            if (t[i-1].s+D<=t[i].s) {t[i].s=t[i-1].s+D; maxn=max(maxn,t[i].s);  }   
             else { maxn=max(maxn,(t[i].s+t[i-1].s+D)/2); }
         }
        else maxn=max(maxn,(t[i].s+t[i-1].s+D)/2); //处理前三种情况
     }
    printf("%d",maxn);//输出
}