P11232 [CSP-S 2024] 超速检测

· · 题解

好多大佬用的二分寻找超速区间，于是我用了双指针。

思路分析

可以把三个特殊性质的代码写出来拼到一起就好了。

性质 A

保证 a_i=0。

如果全部不加速只需要开最后一个点，但不可以开其他的点，因为可能有的车上道路时已经超过了前面的点。

你吃席的原因可能是：

于是二十分的局部函数就出来了：

void subtaskA()
{
    //p保证了有序，最后一个测速点就是p[m]
    int ans1=0;//超速车的数量
    int ans2=m;//可以关闭多少台
    for(int i=1;i<=n;i++)
    {
        //超速了且在最后测速点之前抄的
        if(v[i]>V && d[i]<=p[m])
        {
            ans1++;
        }
    }
    if(ans1!=0)
    {
        ans2--;
    }
    cout<<ans1<<" "<<ans2<<"\n";
}

性质 A+B

保证 a_i >0。

车一直在加速，那如果会在中途被判为超速，那么最后一个测速仪也会判超速。

因为 a_i=0 直接套公式不影响结果，所以可以把两种性质拼起来。

bool check(int d,int v,int a,int p)
{
    if(d>p)
    {
        return false;
    }
    int s=p-d;//位移
    //sqrt(v*v+2*a*s)>V
    return v*v+2*a*s>V*V;
}
void subtaskAB()
{
    //p保证了有序，最后一个测速点就是p[m]
    int ans1=0;//超速车的数量
    int ans2=m;//可以关闭多少台
    for(int i=1;i<=n;i++)
    {
        //超速了且在最后测速点之前抄的
        if(check(d[i],v[i],a[i],p[m])&&d[i]<=p[m])
        {
            ans1++;
        }
    }
    if(ans1!=0)
    {
        ans2--;
    }
    cout<<ans1<<" "<<ans2<<"\n";
}

性质 C

这跟前两个性质的思路大有不同。

保证 a_i <0，且所有车都不在最北端驶离主干道。

你会发现所有车超速都在一个区间内，举个例子比如：

现在要往里面插杆字使得判断出超速尽可能的多。

这是一个很经典的贪心问题：最小点覆盖。

只需要往没插区间的末尾插进去就可以了。

因为这个贪心很板，所以就不证明了。

找区间可以用双指针实现。

代码

#include<bits/stdc++.h>
using namespace std;
int T;
const int MAXN=100000;//MAXM
//车的数量、测速仪数量、主干道长度、限速
int n,m,L,V;
//第i辆车的初始位置、初始速度、加速度
int d[MAXN+5],v[MAXN+5],a[MAXN+5];
//测速点的位置
int p[MAXN+5];
//返回当前属性下的超速区间（位置）
vector<pair<int,int>>line;//所有超速区间
//超速区间按照结束位置排序
bool cmp(pair<int,int>a,pair<int,int>b)
{
    return a.second<b.second;
}
void work()
{
    line.clear();
    //算出所有超速区间
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0)
        {
            //不超速
            if(v[i]<=V)
            {
                continue;
            }
            //整个路程都超速
            line.push_back(make_pair(d[i],L));
        }
        else if(a[i]>0)
        {
            //算算啥时候开始超速
            if(v[i]>V)//一开始就超速
            {
                line.push_back(make_pair(d[i],L));
            }
            else
            {
                //算算走多久之后开始超过V的速度
                //可以想想这里为什么可以规避浮点运算
                int s=(V*V-v[i]*v[i])/(2*a[i])+1;
                if(d[i]+s<=L)
                {
                    line.push_back(make_pair(d[i]+s,L));
                }
            }
        }
        else if(a[i]<0)
        {
            //一开始就不超速，肯定不可能再超速了
            if(v[i]<=V)
            {
                continue;
            }
            //算算最后的超速位置
            //可以想想这里的细节，为什么是上取整减一
            //注意这里不能写+(2*a[i]-1)来实现，因为这边分子分母是负数
            int s=(V*V-v[i]*v[i])/(2*a[i]);
            if((V*V-v[i]*v[i])%(2*a[i])==0)
            {
                s--;
            }
            if(s<0)
            {
                s=0;
            }
            line.push_back(make_pair(d[i],min(L,d[i]+s)));
        }
    }

    sort(line.begin(),line.end(),cmp);
    int pos=1;//下一个考虑的测速点下标
    int last=-1;//最新选上的测速点位置
    int ans1=0;//超速车数量
    int ans2=0;//需要开启的测速点数量
    for(int i=0;i<line.size();i++)
    {
        //如果当前区间已经有启用了的测速点，超速车多一台，不用新测速点
        if(line[i].first<=last)
        {
            ans1++;
            continue;
        }
        //找到最后一个可行的测速点，下一个测速点没超过右端点就变为下一个
        while(pos<m&&p[pos+1]<=line[i].second)
        {
            pos++;
        }
        //看看这个测试点要不要启用
        if(pos<=m && line[i].first<=p[pos] && p[pos]<=line[i].second)
        {
            last=p[pos];//更新最新测速点位置
            pos++;//下一个要考虑后面的测速点了
            ans1++;//这辆车会被检测超速
            ans2++;//选用了一个测速点
        }
    }
    cout<<ans1<<" "<<m-ans2<<'\n';
}
int main()
{
    freopen("detect.in","r",stdin);
    freopen("detect.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>L>>V;
        for(int i=1;i<=n;i++)
        {
            cin>>d[i]>>v[i]>>a[i];
        }
        for(int i=1;i<=m;i++)
        {
            cin>>p[i];
        }
        work();
    }
    return 0;
}