求助！为何6个点WA
原题链接：36089.[CSP-S 2024] 超速检测
2025-10-08 19:55:27
发布于：上海
27阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
struct car{
int d,v,a;
};
// 判断车辆的超速区间[l,r],如果没有超速则返回[-1,-1]
pair<int,int> check(car c,int L,int V){
int d=c.d,v0=c.v,a=c.a;
if(a==0){//匀速直线运动
if(v0>V)
return {d,L};//一开始就超速
return {-1,-1};
}
else if(a>0){//匀加速直线运动
if(v0>V)
return {d,L};
//行驶距离s使得速度达到V,s=(V^2-v0^2)/(2*a);
int num=V*V-v0*v0;
if(num<=0)
return {-1,-1};//永远达不到V
int s=num/(2*a);
if(num%(2*a)!=0)
s++;//避免浮点类型的ceil
if(d+s>L)
return {-1,-1};//到最后都达不到V
return {d+s,L};
}
else{//减速
int num=V*V-v0*v0;
if(num>=0)
return {-1,-1};
//计算停止距离
int s_stop=-v0*v0/(2*a);
if((-v0*v0)%(2*a)!=0)
s_stop++;//依旧上取整
int end=d+min(s_stop,L-d);
int s_pos=d+num/(2*a);//公式，计算不再超速的位置
if(num%(2*a)!=0)
s_pos++;//还是上取整
int s_end=min(end,s_pos);
if(s_end<=d)
return {-1,-1};
return {d,s_end};
}
}
bool cmp(pair<int,int> a,pair<int,int> b){
return a.second<b.second;
}
void solve(){
int n,m,L,V;
car c[MAXN];
vector<int> p;
cin>>n>>m>>L>>V;
for(int i=1;i<=n;i++)
cin>>c[i].d>>c[i].v>>c[i].a;
for(int i=1;i<=m;i++){
int x;
cin>>x;
p.push_back(x);
}
vector<pair<int,int>> speed;
int cnt=0;
for(int i=1;i<=n;i++){
auto [l,r]=check(c[i],L,V);
if(l==-1)
continue;
//检查[l,r]是否有测速仪
auto it=lower_bound(p.begin(),p.end(),l);
if(it!=p.end()&&*it<=r){
cnt++;
speed.push_back({l,r});
}
}
//贪心
sort(speed.begin(),speed.end(),cmp);
int last=-1;
int ccnt=0;
for(auto [l,r]:speed){
if(last<l){
auto it=upper_bound(p.begin(),p.end(),r);
// 没有测速仪在区间内不可能，因为第一问已经保证有
--it;
last=*it;
ccnt++;
}
}
cout<<cnt<<" "<<m-ccnt<<endl;
return;
}
int main(){
//freopen("detect.in","r",stdin);
//freopen("detect.out","w",stdout);
int t;
cin>>t;
while(t--)
solve();
//fclose(stdin);
//fclose(stdout);
return 0;
}
全部评论 3
?
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5 + 10; int n, m, L, V, d[N], v[N], a[N]; vector<int> p; struct Seg { int l, r; // 记录车 i 会被测速仪，检测到超速的区间 [l,r] }; bool cmp(Seg a, Seg b){ return a.r < b.r; } vector<Seg> seg; // 计算瞬间速度 ll speed(ll v, ll a, ll s){ return v * v + 2 * a * s; // 题目已经给出式子 } void handler(int d, int v, int a){ // first 表示进入主干道后第一个碰到的测速仪(下标) int first = lower_bound(p.begin(), p.end(), d) - p.begin(); // 进入主干道，没有遇到测速仪，跳过 if (first >= m) return; // 匀速，那一开始不超速意味着永远不会超速 if (a == 0){ if (v > V) seg.push_back({first, m - 1}); // 如果超速，则加入vector return; } int l = first, r = m - 1, ans = -1, mid; // 减速，找到「最后一个」检测到超速的测速仪 if (a < 0) { while (l <= r) { mid = l + r >> 1; if (speed(v, a, p[mid] - d) > V * V) ans = mid, l = mid + 1; else r = mid - 1; } if (ans != -1) seg.push_back({first, ans}); return; } // 加速，找到「首个」能检测到加速的测速仪 if (a > 0) { while (l <= r) { mid = l + r >> 1; if (speed(v, a, p[mid] - d) > V * V) ans = mid, r = mid - 1; else l = mid + 1; } if (ans != -1) seg.push_back({ans, m - 1}); } } void solve() { p.clear(); seg.clear(); cin >> n >> m >> L >> V; for (int i = 1; i <= n; i++) cin >> d[i] >> v[i] >> a[i]; for (int i = 1, x; i <= m; i++) cin >> x, p.push_back(x); for (int i = 1; i <= n; i++) // 处理每辆车的测速仪超速的区间 handler(d[i], v[i], a[i]); // 区间覆盖问题 sort(seg.begin(), seg.end(), cmp); int last = -1, ans = 0; for (auto it : seg) if (last < p[it.l]) last = p[it.r], ans++; cout << (int)seg.size() << " " << m - ans << "\n"; } int main() { ios::sync_with_st1周前 来自 上海
0
有帮助，赞一个