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

· · 题解

Upd 2024.12.11：修正一处公式错误。\ Upd 2025.7.23： 做了一些修改，调整观感。\ Upd 2025.10.29：更新了一版代码，二分实现改用 bound 函数，码风更为简洁，正文也有些许修改。预祝各位选手 CSP-S2025 复赛顺利。

思路

显然每辆车要么不超速，要么超速在一段连续的区间。二分查找在该区间左端点右侧的第一个测速仪，检查它是否在区间之内就可以判断此车是否超速。

再写一个二分找在区间右端点左侧的第一个测速仪，对于这辆车我们要在这两个测速仪之间（含）的所有测速仪中保留至少一个。参考一道贪心经典题目，这道题甚至还更加简单，已经告诉了你要保留一个。于是就可以 AC 了。

细节实现

求超速区间

唯一需要用到的物理公式如下：

\Delta x=\frac{v^2-v_0^2}{2a}

表达了一段匀变速直线运动中位移 \Delta x、初速度 v_0、末速度 v 和加速度 a 的关系。\ 顺着特殊性质来思考，我们可以分三种情况讨论：

匀速运动：a_i=0

这里还有一个小 trick，我们上面有两种情况实际上是不严谨的，例如超速区间为 (x,L] 和 [d_i,x)，在 x>L 时应该为 \emptyset 和 [d_i,L]，但是这不会影响我们求解，因为没有测速仪在 >L 的位置，所以我们让道路无限长也不会影响这台车是否被抓到。

代码

#include<bits/stdc++.h>
#define ep emplace 
#define eb emplace_back
#define ll long long
#define ull unsigned ll
#define fr(a,b,c) for(int a = (b);a <= (c);a ++)
using namespace std;
template<typename T>void read(T &x){x = 0;int f = 1;char c = getchar();while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)) x = x * 10 + c - '0',c = getchar();x *= f;}
const int N = 200000;
int T,n,m,L,V,d[N],v[N],a[N],p[N],ans,lst;
vector<pair<int,int>> sg;
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> T;
  while(T --){
    sg.clear(),ans = lst = 0;
    cin >> n >> m >> L >> V;
    fr(i,1,n) cin >> d[i] >> v[i] >> a[i];
    fr(i,1,m) cin >> p[i];
    fr(i,1,n){
      int l,r;//要将超速区间表述为整数闭区间 [l,r]
      if(a[i] > 0){
       if(v[i] > V) l = d[i],r = L;//一路超速到尽头
       else l = d[i] + (V * V - v[i] * v[i]) / (2 * a[i]) + 1,r = L;//如果整除，速度到达 V 的瞬间不算超速，左端点应该+1；不整除考虑向上取整，在不整除的情况下就是向下取整再+1
      }
      else if(a[i] < 0){
        if(v[i] > V) l = d[i],r = d[i] + (v[i] * v[i] - V * V - 1) / (-2 * a[i]);//和上面的讨论类似，这里是上取整再-1
        //为了避免负数计算除法向零舍入的讨论，我把上式分子分母取反，变为正数后进行运算
        else continue;//做减速运动，一开始没有超速，就一直不会超速
      }
      else{
        if(v[i] > V) l = d[i],r = L;//一路超速到尽头
        else continue;
      }
      int X,Y;//将 [l,r] 转化为测速仪数列 p 上的区间 p[x...y]
      X = lower_bound(p + 1,p + m + 1,l) - p;
      Y = upper_bound(p + 1,p + m + 1,r) - p - 1;
      if(X <= Y) sg.eb(X,Y);
    }
    sort(sg.begin(),sg.end(),[](pair<int,int> a,pair<int,int> b){
      return a.second < b.second;
    });//按右端点排序
    for(auto [l,r] : sg) if(lst < l) ans ++,lst = r;//贪心过程
    printf("%d %d\n",int(sg.size()),m - ans);
  }
  return 0;
}

总结

主要考察二分和贪心法，码量及实现难度不算太大；但是解题或需一些高中物理思维，对于低龄选手难度会增大。