题解：P11232 [CSP-S 2024] 超速检测

guoziyang21 · 2024-10-26 22:07:48 · 题解

题面

【题目链接】

CSP-S 2024 T2

【题目大意】

有一条最高限速为 V ，长为 L 的主干道，上有 m 个测速仪，其中第 j 个到道路最南端的距离为 p_j ，每个测速仪可以设置为开启或关闭。开启的测速仪可以对经过的车（包括恰好驶入和驶出主干道的车）进行测速，如果这辆车的瞬时速度超过了限速 V ，那么这辆车被判定为超速。

有 n 辆车，其中第 i 辆车将在 d_i 的位置驶入主干道，初速度为 v_i ，加速度为 a_i 。当车辆行驶到 L 的位置或速度降为 0 时，认为该车辆驶出主干道。

回答两个问题：

当所有测速仪开启时，将会有多少辆车被判为超速？
关闭尽可能多的测速仪，使得原本被判为超速的车仍然被判为超速。

【数据范围】

题目中出现的所有字母均为整数。

考场思路

由于是匀加速直线运动，所以超速的区间一定是连续的，而且是可以被计算出来的（注意开闭）。
我们可以把超速的区间变成测速仪的分布区间，例如对于样例 1 ，第四辆车的超速区间为 [5,9) ，转换为测速仪的分布区间为 [2,3] 。
第二点的实现：首先对 a_i 的正负分类讨论得到车的超速区间：
在输入 p_i 时，预处理主干道每个位置左侧和右侧距离它最近的测速仪，根据第三点讨论得到车的超速区间后，轻松解决第一小问，然后根据预处理的结果直接转化为测速仪的分布区间（具体流程可参见下方代码）。
于是第二小问可以变成一个多区间的贪心问题：一条长线段上有若干条短线段（可以重叠也可以不完全覆盖长线段），请在长线段上选取尽可能少的点，使得每条短线段上（含端点）都有被选取的点。
贪心的实现：按照右端点排序（从小到大），然后在尽可能少的右端点处开测速仪。

综上，这题有两点，一是计算每辆车的超速区间并转换成测速仪的分布区间，二是贪心。

（橙+橙=绿）

时间复杂度

对于每组数据：

在输入 p_i 时预处理主干道每个位置左侧和右侧距离它最近的测速仪，时间复杂度 O(L+m) 。
计算每辆车的超速区间，并将超速区间转化为测速仪分布区间，由于需要对 a_i 的正负进行讨论，所以常数可能较大，时间复杂度 O(kn) （ k 是待定的常数）。
然后进行贪心，需要对数据进行排序，时间复杂度 O(n\log n) 。

总时间复杂度： O(T(n\log n+m+L)) 。

代码

AC记录

# include<iostream>
# include<cstdio>
# include<algorithm>
using namespace std;

const int N=1e5+2,L=1e6+2;
int t,n,m,l,V,tmp,ans1,ans2;
int d[N],v[N],a[N],p[N];
int lft[L],rgt[L]; //距离最近的测速仪编号 
int ld[N],rd[N]; //每辆车超速区间的左、右端点
int g[N]; //所有超速的车的编号
int id; //后面贪心用的 

bool cmp(int x,int y){
    return rd[x]<rd[y];
}

void solve(){
    //1.常规读入+初始化
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ans1=ans2=0,id=-1;
    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];
        lft[p[i]]=rgt[p[i]]=i; //这一行是2.的步骤，提前到这 
    }
    //2.预处理距离最近的测速仪编号 
    p[0]=0,p[m+1]=l+1;
    for(int i=0;i<=m;++i)
        for(int j=p[i]+1;j<p[i+1];++j)
            lft[j]=i,rgt[j]=i+1;
    //3.计算每辆车的超速区间（本题核心）
    for(int i=1;i<=n;++i){
        if(d[i]>p[m]) continue; //如果驶入的位置之后没有测速仪就不理它了 
        if(a[i]==0){
            if(v[i]>V){
                g[++ans1]=i;
                ld[i]=rgt[d[i]];
                rd[i]=m;
            } //一开始就超速 
        }
        else if(a[i]>0){
            if(v[i]>V){
                g[++ans1]=i;
                ld[i]=rgt[d[i]];
                rd[i]=m;
            } //一开始就超速
            else{
                //开始超速的地方是：d[i]+位移向下取整+1
                tmp=V*V-v[i]*v[i];
                tmp=d[i]+tmp/(2*a[i])+1;
                //对超速的位置判断 
                if(tmp<=p[m]){
                    g[++ans1]=i;
                    ld[i]=rgt[tmp];
                    rd[i]=m;
                } 
            } //加速了一会儿才超速 
        }
        else{
            if(v[i]>V){
                //开始超速的地方是：d[i]+位移向上取整-1
                tmp=v[i]*v[i]-V*V;
                if(tmp%(-2*a[i])==0)
                    tmp=d[i]+tmp/(-2*a[i])-1;
                else
                    tmp=d[i]+tmp/(-2*a[i]);
                //对超速的位置判断
                if(tmp>=p[m]){
                    g[++ans1]=i;
                    ld[i]=rgt[d[i]];
                    rd[i]=m;
                }
                else{
                    ld[i]=rgt[d[i]];
                    rd[i]=lft[tmp];
                    //有可能出现超速区间恰好夹在两个测速仪之间的情况 
                    if(rd[i]>=ld[i]) g[++ans1]=i;
                }
            } //一开始超速，后面减速 
        } 
    }
    //4.计算最少需要开启的测速仪数量（贪心）
    sort(g+1,g+1+ans1,cmp); //按照右端点从小到大排序
    for(int i=1;i<=ans1;++i)
        if(ld[g[i]]>id){
            id=rd[g[i]];
            ++ans2;
        } //如果左端点没有被覆盖到，那就在右端点覆盖 
    cout<<ans1<<" "<<m-ans2<<endl;
}

int main(){
    cin>>t;
    while(t--) solve(); 
    return 0;
}

update：

2024.10.26 完成初稿，提交审核。

2024.11.05 官方数据出来后，对代码进行了简化和重测，对其他内容进行了部分修改。