复赛二：超速检测（detect）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-10-01 20:50:54
 * 最后修改: 2025-10-02 13:49:15
 * 文件描述: 【24CSPS提高组】超速检测
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

// -------------------- 数据结构 --------------------
struct Car{
    int d; // 初始位置（进入道路的位置），题目保证 0 <= d < L
    int v; // 初速度（>0）
    int a; // 加速度（可正、负或 0）
};

// -------------------- 离散点二分工具（基于已升序 cam） --------------------
// 找到第一个 >= x 的摄像头下标；若不存在返回 cam.size()
int first_ge(const vector<int>& cam, double x) {
    // lower_bound 支持和 double 比较（内建算术转换），cam 必须是升序
    return (int)(lower_bound(cam.begin(), cam.end(), x) - cam.begin());
}

// 找到第一个 > x 的摄像头下标；若不存在返回 cam.size()
int first_gt(const vector<int>& cam, double x) {
    return (int)(upper_bound(cam.begin(), cam.end(), x) - cam.begin());
}

// 找到最后一个 <= x 的摄像头下标；若不存在返回 -1
int last_le(const vector<int>& cam, double x) {
    return (int)(upper_bound(cam.begin(), cam.end(), x) - cam.begin()) - 1;
}

// 找到最后一个 < x 的摄像头下标；若不存在返回 -1
int last_lt(const vector<int>& cam, double x) {
    return (int)(lower_bound(cam.begin(), cam.end(), x) - cam.begin()) - 1;
}

// -------------------- 覆盖判定（把物理“超速位置集合”映射为“摄像头下标闭区间 [li,ri]”） --------------------
// 约定：返回 true 表示这辆车在“所有测速仪全开”时会被抓，且输出它能被抓到的摄像头下标范围 [li, ri]（闭区间）。
// 若返回 false，表示无任一开启摄像头能抓到它（要么无超速，要么区间内不含摄像头）。

// a == 0：速度恒定
//   - 若 v0 > V：超速区间为 [d, L]（两端闭；驶入/驶出点也测速）
//   - 若 v0 <= V：无超速
bool cover_a_eq0(const Car& c, int L, int V, const vector<int>& cam, int& li, int& ri) {
    if (c.v <= V) return false;          // 恒速且不超过限速
    li = first_ge(cam, c.d);             // 左端闭：包含 d
    ri = last_le (cam, L);               // 右端闭：包含 L
    return li <= ri;                     // 区间内至少有一个摄像头
}

// a > 0：速度单调上升
//   - 若 v0 > V：超速区间 [d, L]（含 d）
//   - 若 v0 = V：超速区间 (d, L]（不含 d，本题要求严格 >V）
//   - 若 v0 < V：先不超速，超过点 xV = d + (V^2 - v0^2)/(2a)，超速区间 (xV, L]
bool cover_a_pos(const Car& c, int L, int V, const vector<int>& cam, int& li, int& ri) {
    ri = last_le(cam, L);                // 右端统一闭（驶出点也测速）
    if (c.v > V) {                       // [d, L]
        li = first_ge(cam, c.d);
    } else if (c.v == V) {               // (d, L]
        li = first_gt(cam, c.d);
    } else {                             // v0 < V： (xV, L]
        // 用浮点触发浮点除法，避免整数除法截断
        double xV = c.d + (V*V - c.v*c.v) / (2.0 * c.a);  // 这里 a>0，安全
        li = first_gt(cam, xV);              // 左端开：> xV
    }
    return li <= ri;
}

// a < 0：速度单调下降
//   - 若 v0 <= V：起点就不严格超速，且之后只会更慢 → 无超速
//   - 若 v0 > V：从进入点 d 开始超速，直到降到 V 的位置（不含）
//       xV = d + (v0^2 - V^2)/(-2a)  （注意 a<0，分母为正）
//     同时车辆可能先到 L 离开；右端选择：若 xV <= L 用 (xV, 开；否则用 L 闭。
bool cover_a_neg(const Car& c, int L, int V, const vector<int>& cam, int& li, int& ri) {
    if (c.v <= V) return false;          // 一开始就不超速，之后只会降速
    double xV =c.d + (c.v*c.v - V*V) / (-2.0 *c.a); // a<0，-2a>0
    li = first_ge(cam, c.d);             // 左端闭：包含 d
    if (xV <= L) {
        ri = last_lt(cam, xV);           // 右端开：< xV
    } else {
        ri = last_le(cam, L);            // 先到 L 离开：右端闭（包含 L）
    }
    return li <= ri;
}

// 区间排序：按右端升序；右端相同按左端升序
bool cmpInterval(const pair<int,int>& A, const pair<int,int>& B) {
    if (A.second != B.second) return A.second < B.second;
    return A.first < B.first;
}

int main(){
    int T;
    if(!(cin >> T)) return 0;
    while (T--) {
        int n, m, 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<int> cam(m);
        for (int i = 0; i < m; ++i) cin >> cam[i];
        // 题目保证 cam 已升序：0 ≤ p1 < p2 < … < pm ≤ L
        // 如果不放心，可解开下一行：

        vector<pair<int,int>> need;      // 每辆会被抓的车可被抓的摄像头下标闭区间 [li, ri]

        int overspeed_cars = 0;          // 第一问：全开时被判超速的车辆数

        for (const auto &c : cars) {
            int li = 1, ri = 0;
            bool has = false;
            if (c.a == 0) {
                has = cover_a_eq0(c, L, V, cam, li, ri);
            } else if (c.a > 0) {
                has = cover_a_pos(c, L, V, cam, li, ri);
            } else { // c.a < 0
                has = cover_a_neg(c, L, V, cam, li, ri);
            }
            if (has) {
                ++overspeed_cars;
                need.emplace_back(li, ri);
            }
        }

        // 第二问：在不漏掉任何“本应被抓”的车的前提下，最多能关闭多少测速仪？
        // 等价于：从摄像头位置中选最少的点，刺穿 need 中所有闭区间（最小点集覆盖）。
        // 经典贪心：按区间右端升序遍历，若当前已选点 last 不在 [Lidx, Ridx] 内，则选择 Ridx。
        sort(need.begin(), need.end(), cmpInterval);
        int chosen = 0, last = -1;
        for (const auto &seg : need) {
            int Lidx = seg.first;
            int Ridx = seg.second;
            if (last < Lidx) {           // 只有 last 在左边界左侧时才需要新选一个点
                last = Ridx;             // 选该区间最右端的摄像头
                ++chosen;
            }
        }
        int max_close = m - chosen;      // 最大可关闭数量 = 总数 - 必须开启数

        cout << overspeed_cars << ' ' << max_close << "\n";
    }
    return 0;
}