CF534B Covered Path 题解

XL4453 · 2021-12-05 10:57:57 · 题解

提供一种复杂度为 O(1) 的直接计算法。

解题思路：

首先发现，将 v_1 和 v_2 交换并无影响，所以为了方便，直接将 v_1 强制定为相对较小的那一个。

考虑贪心，在能将速度最后降到要求的前提下尽量增加速度，到最后在往下降。

数据范围很小，直接模拟就行了。

但这种只给了几个数的题不优化一下有点过意不去。

前置知识：速度图像中面积表示位移。

若将问题放在实数范围下，也就是没有秒间换速度的限制，问题就可以直接转换为物理中运动中的速度问题，直接用面积法求解，复杂度是 O(1) 的。

回到本题，发现其实更改的就是将整个问题的范围变为高斯函数下的直线交点与面积问题，推一推式子依然可以 O(1) 求出。

推式子：

以时间为 x 轴，速度为 y 轴建立坐标系。

写出两条直线。

解得

这里其实只需要 x，而这个是在实数范围下的，转换一下就是：x=\left\lfloor\dfrac{v_2-v_1+dt}{2d}\right\rfloor。

这个点及其左边都是开满加速度，右边也是，只有这个点到下一个需要考虑到回不来的情况。

分开来算，左边和右边都是等差数列求和：左边面积为 v_1x+\dfrac{dx(x-1)}{2}，右边：v_2(t-x-1)+\dfrac{d(t-x-1)(t-x-2)}{2}，比较简单，不多赘述。

然后考虑最中间一段，肯定是两边较小的一个加满加速度，然后这样一定能到达另一个且总和最大，注意得出这个结论要两方面考虑。这一步的计算需要算出左右两边的速度，然后取最小值，加上 d，还是比较简单的。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int v1,v2,t,d,x,ans,kx,ky;
int main(){
    scanf("%d%d%d%d",&v1,&v2,&t,&d);
    if(v1>v2)swap(v1,v2);//v1<v2
    if(d==0){
        printf("%d\n",v1*t);
        return 0;
    }
    x=(v2-v1+d*t)/(2*d);
    ans+=x*v1+d*(x-1)*x/2;
    ans+=(t-x-1)*v2+d*(t-x-1)*(t-x-2)/2;
    kx=v1+d*(x-1);
    ky=v2+d*(t-x-2);
    if(kx>ky)swap(kx,ky);//kx<ky
    ans+=kx+d;
    printf("%d",ans);
    return 0;
}