自动搬运

查看原文

来自洛谷，原作者为

	Sirius6699 Light'em up

搬运于2025-08-24 22:53:17，当前版本为作者最后更新于2024-01-22 16:07:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：洛谷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++;
    }
}

代码分析：

• $k$ 表示比赛的距离，单位为米。
• $n$ 表示不同的速度值的数量。
• $x$ 表示每个速度值。

• 现在有人要问了：

num=(a-1)*a/2，----什么意思呀？

if(num+(sum-t)*2+t>=k), ----为什么这么写啊？

if(num+sum*2>=k)，----看不懂怎么办？

首先，第一段代码的作用是计算 Bessie 跑完 $a$ 米时的最小时间。 $num$ 表示前 a-1 秒 Bessie 按照最大速度跑步的总路程。就是等差数列求和

接下来，通过不断增加 $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 不能再增加速度。

好了，最后主函数直接不断输入输出就行了！

核心代码：

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!