20分求条必关
查看原帖
20分求条必关
1061129
zxdt楼主2025/8/30 14:08
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,l,v,pos;
int ans,cnt;
struct node{
    int d,v,a;
}s[100010];
struct ssss{
    int p,id;
}b[100010];
bool cmp(node a,node b){
    return a.d>b.d;
}
int c[100010];
void f(int i){//计算测速仪
    if(pos<s[i].d) return ;//如果路上没有测速仪就返回
    /*
    int k=lower_bound(c+1,c+m+1,s[i].d)-c;//查找第一个测速仪?
    b[k].id=1; //标记测速仪
    pos=b[k].p;
    */
    b[m].id=1;
    ans++;
}
void swp(int i){//计算超时区间
    double x=abs(s[i].v*s[i].v-v*v);
    x=x/abs(s[i].a*2);
    x+=s[i].d;
    int k=lower_bound(c+1,c+m+1,s[i].d)-c;
    //cout<<c[k]<<' '<<x<<endl<<endl;
    if(k>m) return ;
    if(c[k]>x) return ;
    ans++;
    if(s[i].a>0&&s[i].v<=v) return ;
    if(pos>x){
        pos=b[k].p;
        b[k].id=1;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>l>>v;
        for(int i=1;i<=n;i++){
            cin>>s[i].d>>s[i].v>>s[i].a;
        }
        for(int i=1;i<=m;i++){
            cin>>b[i].p;
            b[i].id=0;
            c[i]=b[i].p;
        }
        pos=b[m].p;//最后一个测速仪
        sort(s+1,s+n+1,cmp);
        /*
        for(int i=1;i<=n;i++){
            cout<<s[i].d<<' '<<s[i].v<<' '<<s[i].a<<endl;
        }
        cout<<endl;
        */
        ans=0,cnt=0;//初始化
        for(int i=1;i<=n;i++){
            if(s[i].a==0&&s[i].v>v){
                //if(pos<s[i].d) continue;
                //int k=lower_bound(c+1,c+m+1,s[i].d)-c;
                //b[k].id=1;  
                f(i);
            }
            else if(s[i].a<0&&s[i].v>v){
                swp(i);
            }
            else if(s[i].a>0){
                if(s[i].v>=v) f(i);
                else swp(i);
            }
            //cout<<i<<' '<<ans<<endl;
        }
        for(int i=1;i<=m;i++){
            if(b[i].id){
                cnt++;
                //cout<<b[i].p<<' ';
            }  
        }
        //cout<<endl;
        cout<<ans<<' '<<m-cnt<<endl;
    }
    return 0;
}
2025/8/30 14:08
加载中...