前言

寄!

算法

计算超速区间

容易发现可以计算出每一辆车的超速区间
分讨策略大致如下

void Calc(int Now)
{
    if (Car[Now].v > V)
    {
        if (Car[Now].a >= 0)
        {
            Car[Now].Left = Car[Now].d, Car[Now].Right = L;
            return;
        }
        else
        {
            Car[Now].Left = Car[Now].d;
            Car[Now].Right = (int)(std::min(double(L), double(Car[Now].d) + (double)((V * V) - (Car[Now].v * Car[Now].v)) / (2 * Car[Now].a)));
            if (((V * V) - (Car[Now].v * Car[Now].v)) % (2 * Car[Now].a) == 0)
            {
                Car[Now].Right--;
            }
            return;
        }
    }
    else
    {
        if (Car[Now].a > 0)
        {
            Car[Now].Left = ((int)(double(Car[Now].d) + (double)((V * V) - (Car[Now].v * Car[Now].v)) / (2 * Car[Now].a)) > L) ? 0 : (int)(double(Car[Now].d) + (double)((V * V) - (Car[Now].v * Car[Now].v)) / (2 * Car[Now].a));
            if (((V * V) - (Car[Now].v * Car[Now].v)) % (2 * Car[Now].a) == 0 && Car[Now].Left != 0)
            {
                Car[Now].Left++;
            }
            Car[Now].Right = (Car[Now].Left == 0) ? 0 : L;
            return;
        }
        else
        {
            Car[Now].Left = 0, Car[Now].Right = 0;
            return;
        }
    }
}

求解第一问

被测速仪判断到的条件是

考虑二分求每个车辆能否被记录到, 并记录

求解第二问

现在有一些区间, 有一些点, 要选择一些点, 使得所有区间都分别至少包括一个点, 满足上述要求时, 需要最小化选点数量

考虑贪心 (以下考虑的区间都在第一问中被标记为会被记录)
将左端点排序, 从大往小扫, 记录当前选上的最小位置测速仪 \(P\)

若 \(P\) 没法检测到这个区间
再选上最小的大于等于区间左端点的测速仪, 更新 \(P\)

最后输出 \(M - \text{NUM}_{\text{must choose}}\) 即可

代码

后补

总结

这次没见过这种贪心, 分讨的严谨性还是很好的