[CSP-S 2024] 超速检测（二分+大模拟）

题目传送门https://www.luogu.com.cn/problem/P11232都怪比赛时的自己太懒了，只做了特殊性质 A 的 20 pts。

解题思路

首先，我们可以把每辆超速的车的超速区间算出来（这个可以用二分解决）。

这样可以解决第一个小问（有多少辆车会被测出超速）。

对于第二个小问，我们可以做一个类似于线段覆盖的贪心……

先把区间的右端点从小到大排个序，对于一个区间的左端点 ，如果我们前面选的区间的右端点  是  的话，那么就需要选上这个区间。

思路很容易想到，但是代码有点小长，请耐心阅读。

代码

#include<bits/stdc++.h>
using namespace std;
#define double long double
int q;
int n,m,l;
double v;
int p[100001];
struct car{
	int d;
	double v,a;
	//从d驶入，初始速度v,加速ai 
}a[100001];
struct node{
	int l,r;
}qp[100001];
int cnt,ans;
double speed(double v0,double ai,double s)//计算瞬时速度 
{
	if(v0*v0+2.0*ai*s<0)return 0;
	return sqrt(v0*v0+2.0*ai*s);
}
bool cmp(node x,node y)
{
	if(x.r==y.r)return x.l<y.l;
	return x.r<y.r;
}
void erfen()
{
	int ll,rr,mid;
	int wz,qd;

	for(int i=1;i<=n;i++)
	{
		if(a[i].v-v<=0.0&&a[i].a<=0)continue;//这些车是绝对不超速的 
		
		if(a[i].a>0)//ai>0的情况 
		{
			ll=1,rr=m;
			wz=-1;
			qd=-1;
			while(ll<=rr)//二分出车辆驶入后第一个遇到的测速仪 
			{
				mid=(ll+rr)>>1;
				if(p[mid]>=a[i].d)
				{
					qd=mid;
					rr=mid-1;
				}
				else
					ll=mid+1;
			}
			if(qd==-1)continue;//如果没有遇到测速仪，那么不超速 
			ll=qd,rr=m;
			while(ll<=rr)//枚举第一个测出这个车超速的测速仪 
			{
				mid=(ll+rr)>>1;
				if(speed(a[i].v,a[i].a,p[mid]-a[i].d)-v>0.0)
				{
					wz=mid;
					rr=mid-1;
				}
				else
					ll=mid+1;
			}
			if(wz!=-1)//统计区间 
			{
				cnt++;
				qp[cnt].l=wz;
				qp[cnt].r=m;
			}
		}
		else{//若ai<=0 
			ll=1,rr=m;
			wz=-1,qd=-1;
			while(ll<=rr)//枚举起点测速仪 
			{
				mid=(ll+rr)>>1;
				if(p[mid]>=a[i].d)
				{
					rr=mid-1;
					qd=mid;
				}
				else
					ll=mid+1;
			}
			if(qd==-1)continue;//同上 
			ll=qd,rr=m;
			while(ll<=rr)
			{
				mid=(ll+rr)>>1;
				if(speed(a[i].v,a[i].a,p[mid]-a[i].d)-v>0.0)//枚举最后一个能测到它超速的测速仪 
				{
					wz=mid;
					ll=mid+1;
				}
				else
					rr=mid-1;
			}
			if(wz!=-1)//统计区间 
			{
				cnt++;
				qp[cnt].l=qd;
				qp[cnt].r=wz;
			}
		}
	}
}
void init()//初始化 
{
	ans=0,cnt=0;
}
int main()
{
//	freopen("detect3.in","r",stdin);
//	freopen("www.txt","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>q;
	while(q--)
	{
		init();
		cin>>n>>m>>l>>v;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].d>>a[i].v>>a[i].a;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>p[i];
		}
		erfen();
		sort(qp+1,qp+cnt+1,cmp);//类似于线段覆盖 
		int temp=0;
		for(int i=1;i<=cnt;i++)
		{
			if(temp<qp[i].l)
			{
				ans++;
				temp=qp[i].r;
			}
		}
		cout<<cnt<<" "<<m-ans<<endl;
	}
}