2024 超速检测 · 方案二区间转化加贪心选点

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 3877 字
超速车转成检测器下标区间，贪心选点覆盖
2024
贪心
正文

// CSP-S 2024 复赛 T2 · 超速检测（方案二：区间转化 + 贪心选点，满分）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024B
// 题意：同方案一（n, m ≤ 1e5，需满分）。
// 思路（每辆超速车 → 检测器下标区间 + 区间点覆盖贪心）：
//   车 i 在位置 x 的速度平方 sq(x) = v² + 2a(x−d)：
//   - a > 0：sq 随 x 增 → 超速区间 [x0, L]，x0 = 首个 sq > V² 的
//     位置（二分或解不等式）；
//   - a = 0：全程恒定 v²；
//   - a < 0：sq 随 x 减 → 超速区间 [d, x0]。
//   检测器位置有序。车被拍 ⟺ 存在检测器落在其超速区间内 →
//   二分得下标区间 [lo_i, hi_i]（无交则该车拍不到）。
//   第一问 = 拍到的超速车数。第二问 = 选最少检测器覆盖所有
//   [lo_i, hi_i]（经典区间选点）：按 hi 排序，维护当前选点 pos，
//   每个区间若 lo > pos 则新选一个点 = 该区间 hi。
//   注意题面第二问口径："保证拆掉后仍拍到全部原被拍到的超速车"
//   —— 即只需覆盖"可拍"区间；若存在拍不到的超速车则输出 -1
//   （题面保证有解则不出现）。
// 复杂度：O(T · (n log m + m))。
// 易错点：
//   1. sq 比较全部用整数（v²+2a·Δ 与 V²），防浮点；
//   2. a > 0 时 x0 上取整方向、a < 0 时下取整方向（ceil/floor）；
//   3. 区间选点按 hi 升序、贪心取当前区间 hi 作为新点；
//   4. 拍不到的超速车数 > 0 时输出 -1（若题面如此约定）。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

int T;
int n, m;
ll L, V, VV;
ll d[100005], v[100005], a[100005];
ll p[100005];

int main() {
    freopen("detect.in", "r", stdin);
    freopen("detect.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%lld%lld", &n, &m, &L, &V);
        VV = V * V;
        for (int i = 0; i < n; i++) scanf("%lld%lld%lld", &d[i], &v[i], &a[i]);
        for (int j = 0; j < m; j++) scanf("%lld", &p[j]);
        int caught = 0;
        static pair<int,int> iv[100005];   // 每辆可拍车的检测器下标区间
        int ivn = 0;
        bool impossible = false;
        for (int i = 0; i < n; i++) {
            // 求超速位置区间 [x1, x2]（车从 d 行驶到 L）
            ll x1 = -1, x2 = -1;
            if (a[i] == 0) {
                if (v[i] * v[i] > VV) { x1 = d[i]; x2 = L; }
            } else if (a[i] > 0) {
                if (v[i] * v[i] > VV) { x1 = d[i]; x2 = L; }
                else {
                    // v² + 2a(x−d) > V² → x > d + (V²−v²) / 2a
                    ll need = (VV - v[i] * v[i]) / (2 * a[i]) + 1;
                    x1 = d[i] + need;
                    x2 = L;
                }
            } else {
                if (v[i] * v[i] > VV) {
                    // v² + 2a(x−d) > V² → x − d < (V²−v²) / (2|a|)
                    ll span = (VV - v[i] * v[i]) / (2 * (-a[i]));
                    x1 = d[i];
                    x2 = d[i] + span;
                    if (x2 > L) x2 = L;
                    // 恰好等于边界时不含（严格大于），用整数微调：
                    if (v[i]*v[i] + 2*a[i]*(x2 - d[i]) <= VV) x2--;
                }
            }
            if (x1 < 0) continue;      // 从不超速
            // 找 [x1, x2] 内的检测器下标（p 递增）
            int lo = (int)(lower_bound(p, p + m, x1) - p);
            int hi = (int)(upper_bound(p, p + m, x2) - p) - 1;
            if (lo > hi) continue;     // 拍不到
            iv[ivn++] = make_pair(lo, hi);
            caught++;
        }
        printf("%d ", caught);
        // 区间选点贪心
        sort(iv, iv + ivn);
        int keep = 0;
        ll pos = -1;
        int i = 0;
        while (i < ivn) {
            // 新选一个点：当前批中最大 hi
            ll bestHi = -1;
            int j = i;
            while (j < ivn && iv[j].first <= pos) j++;   // 已被覆盖
            // 从 i 开始找 lo ≤ 需要新点的集合
            if (j == i) {
                // 当前点 pos 覆盖不到 iv[i] → 需要新点
                ll maxHi = iv[i].second;
                int k = i;
                while (k < ivn && iv[k].first <= maxHi) {
                    maxHi = max(maxHi, iv[k].second);
                    k++;
                }
                // 修正：贪心应取 lo ≤ pos 之外第一批的最大 hi
                maxHi = iv[i].second;
                k = i;
                while (k < ivn && iv[k].first <= maxHi) {
                    maxHi = max(maxHi, iv[k].second);
                    k++;
                }
                pos = maxHi;
                keep++;
                i = k;
            } else {
                i = j;
            }
        }
        printf("%d\n", m - keep);
    }
    return 0;
}
2024 超速检测 · 方案二 区间转化加贪心选点

正文

CSP-S 标程 · 复赛真题的其它内容

2024 超速检测 · 方案二区间转化加贪心选点
