wa #5 #6求调
查看原帖
wa #5 #6求调
562569
kingho11楼主2024/11/25 16:25
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,tp;
long double L,V,p[N];
struct uuu{
	long double d,v,a;
}car[N];
struct uu{
	int l,r;
}a[N];
int lwr(long double x)
{
	int l=1,r=m;
	while(l<r)
	{
		int mid=l+r>>1;
		if(p[mid]*1.0-x>=-0.000000000001)
		{
			r=mid;
		}else
		{
			l=mid+1;
		}
	}
	if(x-p[l]*1.0>0.000000000001) return m+1;
	else return l;
}
int upr(long double x)
{
	int l=1,r=m;
	while(l<r)
	{
		int mid=l+r>>1;
		if(p[mid]*1.0-x>0.000000000001)
		{
			r=mid;
		}else
		{
			l=mid+1;
		}
	}
	if(x-p[l]*1.0>0.000000000001) return m+1;
	else return l;
}
bool cmp(uu a,uu b)
{
	if(a.r==b.r) return a.l<b.l;
	else return a.r<b.r;
}
int ssolve()
{
	sort(a+1,a+1+tp,cmp);
	int r=0,cnt=0;
	for(int i=1;i<=tp;i++)
	{
		if(a[i].l>r)
		{
			cnt++;
			r=a[i].r;
		}
	}
	return m-cnt;
}
void solve()
{
	tp=0;
	cin>>n>>m>>L>>V;
	for(int i=1;i<=n;i++)
	{
		int aa,bb,cc;
		scanf("%d%d%d",&aa,&bb,&cc);
		car[i].d=aa,car[i].v=bb,car[i].a=cc;
	}
	for(int i=1;i<=m;i++)
	{
		int x;
		scanf("%d",&x);
		p[i]=x;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(car[i].a==0 && V-car[i].v>=-0.000000001) continue;
		if(car[i].a==0)
		{
			int l=upr(car[i].d);
			if(l>m || l==-1) continue;
			ans++;
			a[++tp]=(uu){l,m};
		}
		if(car[i].a>0)
		{
			long double s=(V*V-car[i].v*car[i].v)/(2*car[i].a);
            int l;
            if(s<0)
            {
            	l=upr(car[i].d);
			}else
			{
				s+=car[i].d;
		        l=upr(s);//在l这个探测器这里会被查到超速 
			}
			if(l==-1) continue;//不会被查到超速
			if(l>m) continue;
			ans++;
			a[++tp]=(uu){l,m};
		}
		if(car[i].a<0)
		{
			if(V-car[i].v>=-0.0000000001) continue;
			long double s=(V*V-car[i].v*car[i].v)/(2*car[i].a);
			s+=car[i].d;
			int l=lwr(car[i].d),r=lwr(s)-1;
			if(l>r || l==-1 || r<=0) continue;
			ans++;
			a[++tp]=(uu){l,r};
		}
	}
	printf("%d %d\n",ans,ssolve());
}
int main()
{
// 	freopen("detect.in","r",stdin);
// 	freopen("detect.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}
2024/11/25 16:25
加载中...