题解：P11232 [CSP-S 2024] 超速检测（民间数据）

· · 题解

upd：添加更多的补充说明。

upd：删除文章无意义内容。

智慧题。

Solution

直接枚举关掉哪些开哪些显然不可取，考虑预处理出每辆车超速区间。

由于题目中明确指出只需要考虑从南向北的车辆，也就是说初速度 v_0\geq0，于是可以考虑对加速度 a 分三种情况讨论。

注：本篇文章主要只用到了 x=v_0\times t+\dfrac{1}{2}a\times t^2 这个公式。

具体地：

注意，有些区间里可能没有监控，判断一个区间内是否有点可以采用二分实现。具体地，二分找到第一个在区间左端点右方的监控，判断此监控是否包含在区间内即可。

第一步完成，还有第二步。

现在题目转化为了给你 n 个区间，让你选出 k 个点 pos_i，使得对于每条线段都至少存在一个 pos_i 使得 l \leq pos_i \leq r。

这就是典型的贪心模型。考虑按右端点从小到大排序，每次贪心的选尽量靠右端点的监控，具体操作可以通过二分实现。

以上便是该题目的两步操作。

注意到开区间的存在，我们可以考虑给开区间加上或减去一个极小浮点值 eps 来避免。

时间复杂度 O(TN \log N)。

code

upd：更改代码为考场代码。

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr)
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define pre(i, j, k) for(int i = j; i >= k; --i)
#define PII pair<int, int>
#define fi first
#define se second
#define inf 0x3fffffff

using namespace std;

const int N = 1e5 + 5;
const double eps = 1e-8;

struct Cars {
    double d, v, a;
    #define d(p) b[p].d
    #define v(p) b[p].v
    #define a(p) b[p].a
} b[N];

struct node {
    double l, r;
    #define l(p) c[p].l
    #define r(p) c[p].r

    bool operator < (const node &a) const {return r == a.r ? l < a.l : r < a.r;}
} c[N];

int n, m, res;
double L, V, p[N];

void init() {
    res = 0;
//  cin >> n >> m >> L >> V;
    scanf("%d %d %lf %lf", &n, &m, &L, &V);
    rep(i, 1, n) scanf("%lf %lf %lf", &d(i), &v(i), &a(i)), l(i) = r(i) = -1;
    rep(i, 1, m) scanf("%lf", &p[i]);
}

void sol() {
    init(); 
    rep(i, 1, n) {
        if(a(i) == 0) {
//          cout << i << '\n';
            if(v(i) > V) l(i) = d(i), r(i) = L;
        }
        else if(a(i) > 0) {
            if(v(i) > V) l(i) = d(i), r(i) = L;
            else {
                double lt = V - v(i);
                double t = lt / a(i);
                double sum = v(i) * t + 0.5 * a(i) * t * t;
                l(i) = d(i) + sum + eps, r(i) = L;
            }
        }
        else if(a(i) < 0) {
            if(v(i) > V) {
//              cout << i << ' ';
                a(i) = fabs(a(i));
                double lmt = v(i) / a(i);
                double lms = 0.5 * a(i) * lmt * lmt;

                double lt = V;
                double t = lt / a(i);
                double sum = 0.5 * a(i) * t * t;
                l(i) = d(i), r(i) = d(i) + (lms - sum) - eps;
            }
        }
    }
//  cerr<<1;
//  return;
//  exit(0);

    int tot = n; n = 0;
    rep(i, 1, tot) {//检查区间内是否有监控（first question）
//      printf("%.3lf %.3lf\n", d(i), r(i));
        if(l(i) > r(i) || (l(i) == r(i) && r(i) == -1)) continue;
        int id = lower_bound(p + 1, p + 1 + m, l(i)) - p;
        if(id == m + 1) continue;
        if(p[id] > r(i)) continue;
        ++n;
        l(n) = l(i), r(n) = r(i); r(n) = min(r(n), L);
    }

//  cout << n << ' '; 
    printf("%d ", n);
    if(n == 0) return printf("%d\n", m), void();
    sort(c + 1, c + 1 + n);
//  rep(i, 1, n) printf("%.3lf %.3lf\n", l(i), r(i));
    int id = upper_bound(p + 1, p + 1 + m, r(1)) - p - 1;
    double pos = p[id];//开始贪心选点（second question）
//  cout << pos << '\n';
    rep(i, 2, n) {
        if(l(i) <= pos && pos <= r(i)) continue;
        else {
            id = upper_bound(p + 1, p + 1 + m, r(i)) - p - 1;
            pos = p[id];
//          cout << i << ' ' << pos << '\n';
            ++res;
        }
    }
    printf("%d\n", m - res - 1);
//  cout << m - res - 1;
//  cout << '\n';
//  exit(0);
}

signed main() {
//  FASTIO;

//  freopen("detect.in", "r", stdin);
//  freopen("detect.out", "w", stdout); 

    int _; cin >> _;
    while(_--) sol();

    return 0;
}

后记

考场上因为大量输入 double 本地 TLE 了调了很久，cin 输入 double 会非常慢，正确的做法应该是输入 int 在计算时转为 double，将 cin 换为 scanf 读入在本地会快一点，但是实测在各大 OJ 包括 CCF 机子上用 cin 都可以过，可以看我提交记录。