闻灌佬多,求调S组T2
  • 板块灌水区
  • 楼主FireFy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/29 16:50
  • 上次更新2024/10/29 20:12:05
查看原帖
闻灌佬多,求调S组T2
686915
FireFy楼主2024/10/29 16:50

rt,第二问对了,第一问不对

我也不知道我是怎么打出这么抽象的代码的

题目

#include <bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
struct Car
{
	int d,v,a,dl,dr;
	double l,r;
	bool no;
}car[100010];
bool cmp(Car x,Car y)
{
	return x.dl==y.dl?x.dr>y.dr:x.dl<y.dl;
}
bool comp(Car x,Car y)
{
	return x.l<y.l;
}
int p[100010];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
 	//freopen("detect4.in","r",stdin);
 	//freopen("detect.out","w",stdout);
	int i,j,k,n,m,T,L,V;
	cin>>T;
	while(T--)
	{
		memset(car,0,sizeof(car));
		cin>>n>>m>>L>>V;
		for(i=1;i<=n;i++) cin>>car[i].d>>car[i].v>>car[i].a;
		for(i=1;i<=m;i++) cin>>p[i];
		for(i=1;i<=n;i++)
		{
			if(car[i].v>V)
			{
				car[i].l=car[i].d;
				if(car[i].a>=0) car[i].r=inf;
				else car[i].r=car[i].d+(V*V*1.00-car[i].v*car[i].v*1.00)/(2.00*car[i].a);
				if(car[i].l>car[i].r) car[i].no=1;
			}
			else
			{
				if(car[i].a<=0) 
				{
					car[i].l=inf;
					car[i].r=-inf;
					car[i].no=1;
				}
				else
				{
					car[i].l=car[i].d+(V*V*1.00-car[i].v*car[i].v*1.00)/(2.00*car[i].a);
					car[i].r=inf;
				}
			}
		}
		int sum=n;
		for(i=1;i<=n;i++)
		{
			int l=1,r=m,mid;
			while(l<=r)//car[i].dl
			{
				mid=(l+r)/2;
				if(p[mid]>=ceil(car[i].l))
				{
					car[i].dl=mid;
					r=mid-1;
				}
				else l=mid+1;
			}
			l=1,r=m,mid;
			while(l<=r)//car[i].dr
			{
				mid=(l+r)/2;
				if(p[mid]<=ceil(car[i].r))
				{
					car[i].dr=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			if(car[i].dr<=car[i].dl) sum--;
		}
		int ans=0,j=0;
//		for(i=1;i<=n;i++) cout<<car[i].l<<" "<<car[i].r<<endl;
		sort(car+1,car+n+1,cmp);
		int last=-1,minn=inf;
		for(i=n;i>=1;i--)
		{
			if(minn>=car[i].dr) minn=car[i].dr;
			else car[i].no=1;
		}	
		for(i=1;i<=n;i++)
		{
			if(car[i].no)
			{
//				sum--;
				continue;
			}
			if(last<car[i].dl)
			{
				ans++;
				last=car[i].dr;
			}
		}
		cout<<sum<<" "<<m-ans<<endl;
	}
}
2024/10/29 16:50
加载中...