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

· · 题解

这么简单的题，场上居然没切出来qwq

题目链接 P11232 [CSP-S 2024] 超速检测

点击此处获得更佳阅读体验

我觉得这可能是第一篇线性时间复杂度的题解（）

N(同学):为啥要用前缀和？不用二分吗？

K(我):你要明白这其中的逻辑关系，n \le 10^5,L\le 10^6,L<n\log n，所以前缀和比二分快

N:不是还有个排序吗，时间复杂度不还是 n\log n 吗

K:我们可以用计数排序

N:？？？

题目大意

给定n个区间和m个检测点，值域为L，我们希望知道：

  1. 有多少个区间中包含检测点
  2. 删除其中尽可能多的位置，并保证包含检测点的区间数不变

其中 1\le n,m \le 10^5,1\le L\le 10^6 ；

输入包含 T 组数据， T\le 20 。

解题思路

0.理解题意

显然，我们只需要关心我们的超速区间被哪些检测点检测到，也就是说我们需要将每辆车超速的区间转化为每辆车被检测到的检测点区间

示意图：

这期间我们需要做两件事：计算超速区间 和 转换

1.计算超速区间

通过这个公式，我们可以计算出一辆车瞬时速度从 v_0 加速/减速到限速 V 时的位移路程，从而计算出超速区间

具体的说：

  1. 如果 v_0>V 且 a\le0 ，这辆车将一直超速，即 l=d_i,r=L+1 (由于主干道长度只有L所以我们算到L+1即可，不能赋值为INF因为之后要算前缀和)
  2. 如果 v_0\le V 且 a\le0 ，这辆车将永不超速，即 l=L+1,r=L+1
  3. 如果 v_0\le V 且 a>0 ，这辆车将在某一时刻开始超速，直到驶离，即 l=d_i+\left ( \left \lfloor \frac{V^2-v_0^2}{2a} \right \rfloor +1 \right ) ,r=L+1
  4. 如果 v_0>V 且 a<0 ，这辆车将在一开始超速，之后减速直到限速以下，即 l=d_i,r=d_i+\left ( \left \lceil \frac{v_0^2-V^2}{-2a} \right \rceil -1 \right ) (个人感觉这个最容易错qwq)

    2.转换

    注意到值域 L 很小

我们可以使用前缀和维护区间中出现过的检测点数量并计算下标范围

具体的说，检测点区间的左端点为 S_{l-1}+1，右端点为 S_r，S_i 表示位置 i 之前共出现过多少个检测点

时间复杂度为 O(L)

统计非空的区间个数，我们就能得出第一问的答案

对于第二问，我们可以采用贪心的策略

具体的说，对于任意两个检测点区间，若其有交集，则将区间合并为两者交集，最后统计互不相交的区间个数，即为不需要删除的区间数，对总数做差即可求出需要删除的最大区间数

有一个很好的思路可以实现这个过程：先将所有区间按左端点从小到大排序，然后从大到小遍历；对于每个区间，若左侧区间的右端点大于当前区间的左端点，将左侧区间的左端点缩到当前区间的左端点，否则认为该区间与其它区间不相交，不需要删除

由于左端点相同的区间一定会合并，并且值域相当小( m\le 10^5 )，我们可以采用计数排序从而达到线性时间复杂度

代码

AC记录

#include<bits/stdc++.h>
using namespace std;
//时间复杂度：O(T(L+n+m)) 空间复杂度：1e6+3e5
struct gqj{//前期：超过限速的区间  后期：可被检测的检测点区间 
    int l,r;
}c[100005];
int t,n,m,len,V;
int s[1000005];//前缀和
int ji[100005],tp;//计数排序 
int d,v,a;
int sum,ans;
int px;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        for(int i=0;i<=len+1;i++) s[i]=0;//初始化 
        cin>>n>>m>>len>>V;
        for(int i=0;i<=m+1;i++) ji[i]=m+1;//计数排序初始化 
        V*=V;//算出平方 
        for(int i=1;i<=n;i++){
            cin>>d>>v>>a;
            v*=v;//s=(v1^2-v0^2) 
            //注意符号
            if(v<=V&&a<=0){
                c[i].l=len+1; 
                c[i].r=len+1;
            }
            if(v<=V&&a>0){
                c[i].l=min(d+(V-v)/(a<<1)+1,len+1);//ps: a<<1 <==> a*2
                //如果你RE 很可能是这里的锅 
                //注意取整问题 
                c[i].r=len+1;
            }
            if(v>V&&a>=0){
                c[i].l=d;
                c[i].r=len+1;
            }
            if(v>V&&a<0){
                a*=-1;
                c[i].l=d;
                c[i].r=min(d+(v-V+(a<<1)-1)/(a<<1)-1,len+1);
                //如果你WA on #8 #10 可能是取整有问题
                //别问我怎么知道的 
            }
        }
        for(int i=1;i<=m;i++){
            cin>>px;
            s[px]=1;//当前位置有一个测速点 
        }

        for(int i=1;i<=len+1;i++) s[i]+=s[i-1];//前缀和
        //记得算到len+1 后面要用

        sum=0;
        for(int i=1;i<=n;i++){
            if(s[c[i].r]-(c[i].l?s[c[i].l-1]:0)){//三目运算符：条件表达式?如果真则返回:如果假则返回 
                c[i].l=c[i].l?s[c[i].l-1]+1:1;
                c[i].r=s[c[i].r];
                sum++;
            }
            else{
                c[i].l=m+1; 
                c[i].r=m+1;
            }
            ji[c[i].l]=min(ji[c[i].l],c[i].r);//计数排序预处理 
        }
        cout<<sum<<" ";//第一问

        tp=0;//按左端点排序
        for(int i=1;i<=m;i++){//值域1e5计数万岁 
            if(ji[i]!=m+1){
                tp++;
                c[tp].l=i;
                c[tp].r=ji[i];
            }
        }

        ans=m;//删除的点的数量 
        //一开始目害了，写成n了qwq 
        for(int i=tp;i>=1;i--){
            if(c[i-1].r>=c[i].l){
                c[i-1].l=c[i].l;
            }
            else
                ans--;//这个点得留
        }
        cout<<ans<<endl;//第二问 
    }
    return 0;
}