请求帮助
查看原帖
请求帮助
307518
zhengzhuo1106楼主2024/12/12 18:37
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
int T;
int a[100005],d[100005],v[100005],speed[100005];
bool h[100005];
struct car{
	int le,ri;
}cars[100005];
bool cmp(car a,car b){
	if(a.le==b.le)return a.ri<b.ri;
	return a.le<b.le;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		int n,m,L,V;
		cin>>n>>m>>L>>V;
		int ans1,ans2;
		ans1=ans2=0;
		for(int i=1;i<=n;i++){
			cin>>d[i]>>v[i]>>a[i];
			h[i]=0;
		}
		for(int i=1;i<=m;i++)cin>>speed[i];
		for(int i=1;i<=n;i++){
			if(a[i]<=0&&v[i]<=V)continue;
			if(a[i]>0){
				int place;
				if(v[i]>V){
					place=d[i]-1;
				}
				else{
					place=d[i]+(V*V-v[i]*v[i])/(2*a[i]);
				}
				int ll=1,rr=m,num=-1;
				while(ll<=rr){
					int mid=(ll+rr)/2;
					if( speed[mid]>place){
						rr=mid-1;
						num=mid;
					}
					else ll=mid+1;
				}
				if(num==-1)continue;
				ans1++;
				cars[ans1].le=num;
				cars[ans1].ri=m;
			}
			if(a[i]<=0){
				int lefft,rightt;
				lefft=rightt=0;
				//左端点
				int place=d[i];
				int ll=1,rr=m,num=-1;
				while(ll<=rr){
					int mid=(ll+rr)/2;
					if( speed[mid]>=place){
						rr=mid-1;
						num=mid;
					}
					else ll=mid+1;
				}
				if(num==-1)continue;
				lefft=num;
				//右端点
				ll=lefft,rr=m,num=-1;
				while(ll<=rr){
					int mid=(ll+rr)/2;
					double midd=sqrt((v[i]*1.0*v[i]*1.0+(2.0*a[i]*1.0)*(speed[mid]-d[i]*1.0)));
					if(midd>V){
						ll=mid+1;
						num=mid;
					}
					else rr=mid-1;
				}
				if(num<lefft)continue;
				rightt=num;
				ans1++;
				cars[ans1].le=lefft;
				cars[ans1].ri=rightt;
			}
		}
		//贪心
		sort(cars+1,cars+1+ans1,cmp);
		
		int num=INT_MAX,mini=0;
		for(int i=ans1;i>=1;i--){
			if(num<=cars[i].ri){
				h[i]=1;
			}
			num=min(num,cars[i].ri);
		}	
		for(int i=1;i<=ans1;i++){
			if(h[i]!=0){
				h[i]=0;
				continue;
			}
			if(mini<cars[i].le){
				ans2++;
				mini=cars[i].ri;
			}
		}
		cout<<ans1<<" "<<m-ans2<<"\n";
	}
	return 0;
}
2024/12/12 18:37
加载中...