算法标签

• 计算几何
• 物理模拟
• 贪心算法
• 区间覆盖
• 二分查找

题目分析

这是一个结合物理计算和区间覆盖的复杂问题。需要解决两个子问题：

1. 判断每辆车是否超速：计算每辆车在哪些路段会超速
2. 最大关闭测速仪数量：转化为区间覆盖问题

核心思路

问题1：判断超速车辆

对于每辆车，需要计算其超速区间：

1. 计算驶离位置：

   • 如果 a ≥ 0：end = L（到达北端）
   • 如果 a < 0：end = min(L, d + (0 - v²)/(2a))（速度降为0或到达北端）

2. 计算超速区间：

   • 如果 v > V：起点为 d
   • 否则：解方程 v² + 2a·s = V² 得超速起点
   • 超速终点：解方程 v² + 2a·s = V² 得超速终点（受end限制）

3. 判断是否有测速仪在超速区间内

问题2：最大关闭测速仪数量

转化为区间覆盖问题：

• 每辆超速车对应一个超速区间
• 每个测速仪是一个点
• 要求：每个超速区间内至少保留一个测速仪
• 目标：删除尽可能多的测速仪

算法步骤

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

const double EPS = 1e-9;

struct Car {
    double d, v, a;
};

// 计算车辆的超速区间
pair<double, double> getSpeedingInterval(const Car& car, double L, double V) {
    // 计算驶离位置
    double end_pos = L;
    if (car.a < 0) {
        double stop_pos = car.d - car.v * car.v / (2 * car.a);  // 速度降为0的位置
        if (stop_pos > car.d && stop_pos < L) {
            end_pos = stop_pos;
        }
    }
    
    if (car.v > V) {
        // 起始就超速
        if (car.a == 0) {
            return {car.d, end_pos};  // 匀速，全程超速
        }
        
        // 计算何时速度降到V以下
        double s_slow = (V * V - car.v * car.v) / (2 * car.a);
        double slow_pos = car.d + s_slow;
        
        if (car.a > 0) {
            // 加速，一直超速到终点
            return {car.d, end_pos};
        } else {
            // 减速，超速到slow_pos
            return {car.d, min(end_pos, slow_pos)};
        }
    } else {
        // 起始不超速
        if (car.a <= 0) {
            return {-1, -1};  // 减速或匀速，永远不会超速
        }
        
        // 加速，计算何时开始超速
        double s_start = (V * V - car.v * car.v) / (2 * car.a);
        double start_pos = car.d + s_start;
        
        if (start_pos >= end_pos) {
            return {-1, -1};  // 在超速前就驶离
        }
        
        return {start_pos, end_pos};
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        double L, V;
        cin >> n >> m >> L >> V;
        
        vector<Car> cars(n);
        for (int i = 0; i < n; i++) {
            cin >> cars[i].d >> cars[i].v >> cars[i].a;
        }
        
        vector<double> sensors(m);
        for (int i = 0; i < m; i++) {
            cin >> sensors[i];
        }
        
        // 问题1：统计超速车辆
        vector<pair<double, double>> intervals;
        int speeding_cars = 0;
        
        for (const auto& car : cars) {
            auto interval = getSpeedingInterval(car, L, V);
            if (interval.first < interval.second - EPS) {
                // 检查区间内是否有测速仪
                auto it = lower_bound(sensors.begin(), sensors.end(), interval.first);
                if (it != sensors.end() && *it <= interval.second + EPS) {
                    speeding_cars++;
                    intervals.push_back(interval);
                }
            }
        }
        
        // 问题2：区间覆盖贪心
        sort(intervals.begin(), intervals.end(), const auto& a, const auto& b {
            return a.second < b.second;
        });
        
        int keep = 0;
        int last_used = -1;
        
        for (const auto& interval : intervals) {
            // 找到第一个在区间内的测速仪
            auto it = lower_bound(sensors.begin(), sensors.end(), interval.first);
            if (it != sensors.end() && *it <= interval.second + EPS) {
                int idx = it - sensors.begin();
                if (idx > last_used) {
                    keep++;
                    last_used = idx;
                }
            }
        }
        
        cout << speeding_cars << " " << m - keep << "\n";
    }
    
    return 0;
}

复杂度分析

• 问题1：O(n log m) - 每辆车需要二分查找测速仪
• 问题2：O(k log m) - k为超速车辆数，区间排序和贪心覆盖
• 总复杂度：O(T × (n log m))，适合 n, m ≤ 10⁵

关键点

1. 精度处理：使用double和适当容差EPS
2. 物理公式正确应用：特别注意加速度正负号的处理
3. 边界情况：a=0的特殊处理，区间端点的包含关系
4. 贪心策略：按右端点排序，选择最左的可用测速仪

这个解法能够正确处理各种加速度情况，并给出最优的测速仪关闭方案。