P9948 [USACO20JAN] Race B 题解

· · 题解

备赛USACO25JAN祭

P9948 [USACO20JAN] Race B 题解

题面分析

零帧起手从 0\space m/s 开始，每秒有三种决策：

当冲过 K\space m 的终点时，速度不得超过 X\space m/s。求符合题意的最小时间。

解法分析

首先，为了使时间最小化，我们不会且不可以随意减速。

那只要还没到终点，我们就放肆加速，这样时间肯定是最小的。然而终点限速为 X\space m/s，那我们还需要适时开始减速。整个运动过程的速度-时间图象大体如下所示。

然而求完成这个距离的时间显然不好写程序，那我们倒过来，求运动多少秒会达到甚至超出这个距离呢？

因为是先加速后减速，所以一定存在一个最大速度 maxv。本题的最巧妙的处理来了：

当我们两个阶段的距离之和第一次大于等于题面的距离时，就说明我们找到了最小的 maxv（再小一点就还跑不到），此时我们所累加的时间就是答案。

设两个变量 updis 和 downdis 表示加速、减速两个阶段各自运动的距离。一开始先累加 updis，当当前速度大于等于 X 时开始两个变量一起累加（我们把减速倒过来变成从 X 到 maxv 的加速了），累加到距离之和大于等于 K 时就退出，返回累加得到的时间，搞定！

我们打一下样例的数据表验证一下：

k = 10  x = 1
updis   downdis t
1   0   1
1   1   2
3   1   3
3   3   4
6   3   5
6   6   6

k = 10  x = 2
updis   downdis t
1   0   1
3   0   2
3   2   3
6   2   4
6   5   5

k = 10  x = 3
updis   downdis t
1   0   1
3   0   2
6   0   3
6   3   4
10  3   5

k = 10  x = 4
updis   downdis t
1   0   1
3   0   2
6   0   3
10  0   4

k = 10  x = 5
updis   downdis t
1   0   1
3   0   2
6   0   3
10  0   4

这个\t的支持太糟糕了

我们发现，其实这个题目包含三种情况：

表现在图像上是三段运动，即加速、以 maxv 匀速、减速三段。这是因为我们是 OI，时间是量子化的（不连续的，以整数变化），直接转折的 maxv 那个时刻是小数，取不到，就只能匀速一段时间了。

表现在图象上是直接转折，两段运动。就是取得到 maxv 的情况。

  1. 从头到尾 downdis 就没累加过，只加了 updis 就退出了（如样例第 4,5 组数据）。

在图象上就是一条直线往上冲，不转折向下了。

你想，如果还没加速到 X\space m/s，我们就到终点了，那还减速干什么？

如果正面讨论这三种情况，那该多么痛苦！我们的 maxv 又如何求解呢？然而我们的代码没有众多的特判，一个函数优雅的解决了这两个问题。化繁为简，这就是信息学竞赛的魅力吧。:-)

算法分析

没有二分，没有数学，算不上贪心，我们就是小模拟。

题目有 n 个 X，每个 X 处理的时间 t 有：

\begin{aligned} \frac{0+maxv}{2}\times t+\frac{X+maxv}{2}\times t&=K\\ t\times(maxv+\frac{X}{2})&=K\\ \therefore t&=\frac{K}{maxv+\frac{X}{2}} \end{aligned}

所以复杂度为 O(\frac{K}{maxv+\frac{X}{2}})，由于后面是两个变量一起累加的，这个上界跑不满。

总时间复杂度为 \Theta(n\frac{K}{maxv+\frac{X}{2}})。当数据最糟：距离为 10^9\space m，且最终 X=1\space m/s 时，我们算得的 t=63245。算上 n=1000，总运算量约为 6 \times 10^7。

\therefore$ 这个时间复杂度足以通过本题。$\Box

源码分享

#include<bits/stdc++.h>
using namespace std;

int solve(int dis,int maxv)
{
    int ans=0;
    int updis=0,downdis=0;
    int v=0;
    //cout<<"k = "<<dis<<"\tx = "<<maxv<<endl;
    //cout<<"updis\tdowndis\tt\n";
    while(1)
    {
        v++;
        updis+=v;
        ans++;
        //cout<<updis<<'\t'<<downdis<<'\t'<<ans<<endl;
        if(updis+downdis>=dis)return ans;//累加一个就退出
        if(v>=maxv)
        {
            downdis+=v;
            ans++;
            //cout<<updis<<'\t'<<downdis<<'\t'<<ans<<endl;
            if(updis+downdis>=dis)return ans;//累加两个才退出
        }
    }
}

int main()
{
    int k=0,n=0;
    cin>>k>>n;
    for(int i=1;i<=n;i++)
    {
        int x=0;
        cin>>x;
        cout<<solve(k,x);
        if(i<n)cout<<endl;
    }
    return 0;
}

参考链接

官方题解

感谢希沃白板满足了我画图软件的需求（