社区讨论
马蜂良好70pts,wa 6,9,10
P11232[CSP-S 2024] 超速检测参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mhj0i9ku
- 此快照首次捕获于
- 2025/11/03 18:43 4 个月前
- 此快照最后确认于
- 2025/11/03 18:43 4 个月前
不知道是不是精度问题
CPP#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
const int N = 1e5 + 6;
const 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) {
double v2 = std::sqrt(2 * a[i] * (L - d[i]) + v[i] * v[i]);// 区间尾部的速度
if (v2 > V) {
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) {
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;
} else {
p1[i] = p2[i] = -1;
}
}
}
int 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 条回复,欢迎继续交流。
正在加载回复...