P9948 [USACO20JAN] Race B

 题目大意
Bessie 在跑步，总共有 $K$ 米，一开始速度为 $0$，每秒钟可以将速度增加 $1$ 米每秒，或者减少 $1$ 米每秒，或者速度不变。并要求到达终点时的速度不超过 $X$ 米每秒，问最少要花多少时间。

算法筛选
1. 一开始想到贪心，可不知道什么时候开始降速，不可取。
2. 接下来想一下动态规划，可是数据范围较大，数组开不下，不可取。
3. 二分，貌似看起来没什么问题，判断是否有单调性，只要时间给的够多那达成题目要求的几率就会更大，单调性也有了，所以采用二分解决本题。

速度变化轨迹
很简单的贪心，我们想让时间尽可能少就说明想让速度尽可能快，但要满足到达终点时速度不超过 $X$ 米每秒，所以变化轨迹是一个梯形或者一个三角形，梯形的上底是速度最快的部分，左边的腰是速度在上升的部分，右边的腰是速度在下降的部分。三角形就是将速度最快的部分的时间被迫压缩到了 $1$。

判断是否合法
判断答案是否合法是二分中非常重要的环节，我们分为两个大类讨论。

1. 我们设二分到的答案是 $mid$，这种情况是不管怎么加速最后都超不过 $X$。也就是 $mid \\le X$ 的情况，因为每秒钟最多只能提升 $1$ 米每秒。
2. 正常情况，就是在速度变化轨迹中说到的情况，现在只需要求出在整个运动过程中的最大速度是多少就可以了。我们设最大速度为 $x$，就可以得到以下的方程。
3.
$$
x + x – mid + 1 = t
$$

$$
x = \\frac{t+mid-1}{2}
$$

该计算距离，因为每秒速度最多只能变化 $1$，现在就成了几个等差数列组成，通过算出的 $x$ 辅助分层，因为 $x$ 在梯形或三角形的顶端所以通过找出速度为 $x$ 米每秒的距离的左端点和右端点作为临界点即可完成分层，再使用等差数列求和公式计算就可以算出在时间为 $mid$ 秒时最多可以跑多少的距离。如果距离满足要求记录答案并寻找更优解，否则将 $mid$ 调大。

## 关键代码

bool check(int z,int t){
    if(z<=t){//第1种情况
        if(((z+1)*z)/2>=k){
            return true;
        }
        else{
            return false;
        }
    }
    int s=(z+t)/2;
    int ss=0;//用于存储距离
    if((z+t)%2==1){
        ss+=cmp(1,s);//cmp用于处理1~s的等差序列求和
        ss+=cmp(s,t);
    }
    else{
        ss+=cmp(1,s);
        ss+=cmp(s-1,t);
    }
    if(ss>=k){//判断是否合法
        return true;//满足条件
    }
    else{
        return false;//不满足
    }
}