题解：洛谷P9948 [USACO20JAN] Race B
Sirius6699
·
·
题解
题解：洛谷P9948 [USACO20JAN] Race B
蒟蒻第一篇题解，看题面点这里
题目大意：
Bessie 以 0 米每秒的起始速度，用整数秒时间跑 K 米，每秒可以将速度增加 1 米、保持或减少 1 米，在终点时速度不超过 X 米每秒。计算对于 N 个不同的 X 值，跑完的最短时间。
普通版思路：
这道题的分我们一步一步拿。
首先，如果她一直加速，最后速度可能也没有超过 X，因此我们先算出直线加速到终点时的速度：
while(MIN<k)
//如果MIN小于k则将MIN加上i，最后将MIN的值重新赋为i-1。
{
MIN+=i;
i++;
}
MIN=i-1;
分数到账。
然后我们定义一个函数 time 来处理其他情况：
int time(int a)
{
if (a>=MIN) return MIN;
int num=(a-1)*a/2;
int sum=0;
t=a;
while(1)
{
sum+=t;
if(num+(sum-t)*2+t>=k)
{
ans=a-1+(t-a)*2+1;
/*题目要求， Bessie 的速度不能超过 X ，
所以需要将速度从 t 降低到 t-1 ，再降低到 t-2 ，直到降低
a。所以最小时间为 a-1+(t-a)*2+1 。*/
return ans;
}
if(num+sum*2>=k)
{
ans=a-1+(t-a+1)*2;
/*此时 Bessie 的速度可以保持不变，
最小时间为 a-1+(t-a+1)*2 。*/
return ans;
}
t++;
}
}
代码分析：
num=(a-1)*a/2，----什么意思呀？
if(num+(sum-t)*2+t>=k), ----为什么这么写啊？
if(num+sum*2>=k)，----看不懂怎么办？
首先，第一段代码的作用是计算 Bessie 跑完 a 米时的最小时间。
接下来，通过不断增加 $t$ 的值，$sum$ 。在每次循环中，判断根据当前累加和和已知的 $num$ 值，是否满足条件：
- 如果 `num+(sum-t)*2+t>=k`，表示在当前累加和的基础上继续增加 $t$ 的值，加上前面的累加和，可以超过或等于 $k$ 。那么此时的最小时间 $ans$ 等于 `a-1+(t-a)*2+1`，**即当前 $a$ 米距离的最小时间再加上后面 `t-a` 米距离的最小时间再加上 $1$ 秒**。（因为在尝试增加 $t$ 的值之后，Bessie 可以选择增加速度使得总时间不变）。
- 如果 `num+sum*2>=k`，表示在当前累加和的基础上继续增加 $t$ 的值，可以超过或等于 $k$ 。那么此时的最小时间 $ans$ 等于 `a-1+(t-a+1)*2`，**即当前 $a$ 米距离的最小时间再加上后面 `t-a+1` 米距离的最小时间**。这里不需要额外增加 1 秒，因为在尝试增加 $t$ 的值之后，Bessie 不能再增加速度。
------------
好了，最后主函数直接不断输入输出就行了！
## 核心代码：
```cpp
signed main()
{
// using namespace std;
/*-------------关闭同步流-------------*/
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
/*------------------------------------*/
cin>>k>>n;
int i=1;
while(MIN<k)/*如果MIN小于k则将MIN加上i，最后将MIN的值重新赋为i-1。*/
{
MIN+=i;
i++;
}
MIN=i-1;
FOR(i,1,n)
{
cin>>x;
cout<<time(x)<<endl;
}
return 0;
}
```
------------
以上就是本题的**基本思路**，但一些大佬会觉得这题解~~太水了，又唠叨，~~ 不严谨，那么......
## 数学版思路
**思维难度有点大**
**可以跳过！**
对于每个固定的 $X$，Bessie 想要花费恰好整数秒完成比赛，因此可以考虑使用数学方法进行求解。
首先考虑当速度为 $t$ 时，Bessie 跑了多少米。在第 $i$ 秒，她的速度为 $v_i$，那么她跑的距离为 $v_1+v_2+...+v_i$ 米。显然，$v_1=0$，因此 $v_2=v_3=...=v_{t+1}=1,v_{t+2}=v_{t+3}=...=v_{2t}=2$，以此类推，$v_{(k-1)t+1}=v_{(k-1)t+2}=...=v_{kt}=t$。
可以发现，当速度为 $t$ 时，经过 $t-1$ 秒后 Bessie 的速度从 $0$ 增加到 $t$，并且跑了 $\frac{(t-1)t}{2}$ 米；经过 $t$ 秒后，Bessie 的速度保持不变，跑了 $t^2$ 米；经过 $t+1$ 秒后，Bessie 的速度从 $t$ 减少到 $t-1$，并且跑了 $t^2+t$ 米；经过 $t+2$ 秒后，Bessie 的速度从 $t-1$ 减少到 $t-2$，并且跑了 $t^2+2t$ 米，以此类推。
因此要求出 Bessie 在速度为 $t$ 时，第 $k$ 米的位置。当 Bessie 的速度在 $[1, t]$ 区间内逐渐增加时，她跑的距离为 $\frac{(t-1)t}{2}+(t^2)+(t^2+t)+...+[t^2+(k-(t-1)t-1)t]$，即 $\frac{(t-1)t}{2}+t^2(\lfloor\frac{k}{t}\rfloor-t+\frac{2}{t})+\frac{(k-(t-1)t-1)(k-(t-1)t)}{2}$ 米。
当 Bessie 的速度在 $[t, X]$ 区间内保持不变时，她跑的距离为 $\frac{(t-1)t}{2}+t^2(\lfloor\frac{k}{t}\rfloor-t+1)$ 米。
最后再考虑当速度为 $t-1$ 时，Bessie 跑了多少米。速度为 $t-1$ 时，当 Bessie 跑完 $k$ 米时，她的速度为 $t$，因此可以使用之前的公式计算。但是需要注意的是，在速度从 $t-1$ 降低到 $t$ 的时刻，Bessie 的速度必须小于等于 $X$，因此需要将速度从 $t$ 降低到 $t-1$，再降低到 $t-2$，直到降低到 $a$。因此最小时间为 $a-1+(t-a)\times2+1$。
## 完结撒花！Bye!