社区讨论

玄关求条!马蜂良好,90pts,wa on 6

P11232[CSP-S 2024] 超速检测参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhj01cox
此快照首次捕获于
2025/11/03 18:30
4 个月前
此快照最后确认于
2025/11/03 18:30
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

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

struct segment {
    i64 l, r;
};

i64 n, m, L;
long double V;
long double d[N], v[N], a[N];
long double p1[N], p2[N];// 开始超速位置,结束超速位置
i64 l[N], r[N];// 可以检测到第 i 辆车的区间
long double p[N];
segment line[N];

void solve() {
    std::cin >> n >> m >> L >> V;
    for (int i = 1; i <= n; i++) {
        std::cin >> d[i] >> v[i] >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        std::cin >> p[i];
    }

    std::sort(p + 1, p + 1 + m);
    p[m + 1] = L + 1;

    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) {
            if (v[i] > V) {
                p1[i] = d[i];
                p2[i] = L;
            } else {
                p1[i] = p2[i] = -1;
            }
        } else if (a[i] > 0) {
            long double v2 = std::sqrt(2 * a[i] * (L - d[i]) + v[i] * v[i]);// 区间尾部的速度
            if (v2 > V) {
                long double t = std::max((long double)0, (V - v[i]) / a[i]);
                p1[i] = d[i] + v[i] * t + 0.5 * a[i] * t * t + eps;
                p2[i] = L;
            } else {
                p1[i] = p2[i] = -1;
            }
        } else {
            if (v[i] > V) {
                long double t = (V - v[i]) / a[i];// 降到 V 的时间
                p1[i] = d[i];
                p2[i] = std::min((long double)L, d[i] + v[i] * t + 0.5 * a[i] * t * t - eps);//区别:把eps放进去了
            } else {
                p1[i] = p2[i] = -1;
            }
        }
    }

    i64 cnt = 0;
    for (int i = 1; i <= n; i++) {
        auto it1 = std::lower_bound(p + 1, p + 1 + m, p1[i]);
        auto it2 = std::upper_bound(p + 1, p + 1 + m, p2[i]);
        // std::cout << it1 - p << ' ' << it2 - p << '\n';
        int got = it2 - it1;
        // std::cout << i << ' ' << got << '\n';
        if (got) {
            cnt++;
            l[i] = it1 - p;
            r[i] = it2 - p - 1;
            r[i] = std::min(r[i], m);
            line[cnt].l = l[i];
            line[cnt].r = r[i];
        } else {
            l[i] = r[i] = -1;
        }
    }

    std::cout << cnt << ' ';

    // for (int i = 1; i <= n; i++) {//写对了!!!!!
    //     std::cout << std::fixed << std::setprecision(8) << p1[i] << ' ' << p2[i] << '\n';
    // }

    // for (int i = 1; i <= cnt; i++) {
    //     std::cout << '(' << line[i].l << ',' << line[i].r << ')' << '\n';
    // }

    std::sort(line + 1, line + 1 + cnt, [](segment a, segment b) {
        return a.l < b.l;
    });

    i64 ans = 0, pos = -1;
    for (int i = 1; i <= cnt; i++) {
        if (line[i].l <= pos) {
            pos = std::min(pos, line[i].r);
        } else {
            ans++;
            pos = line[i].r;
        }
    }

    std::cout << m - ans << '\n';
}

int main(){
    std::cin.tie(nullptr) -> sync_with_stdio(false);

    int t;
    for (std::cin >> t; t--; ) {
        solve();
    }

    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...