50pts求调
查看原帖
50pts求调
1394167
li00000000a楼主2024/10/31 19:14
//在计算之前,先将数组memset,再进行下一步操作
//推出来的数学算式要准确,尽量不要有不精确的情况 
//不符合条件的都严格满足其补集 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=1e5+10;
int T,n,m,L,V;
int d[N],v[N],a[N],p[N];
pii use_p[N];
int cl[N],cr[N];
int cnt=0;
int ans_car=0,ans_p=0;
void sol1(){
	pii pl;
	for(int i=1;i<=n;i++){
		if(cl[i]==-1) continue;//注意不存在的区间 
		pl.first=lower_bound(p+1,p+m+1,cl[i])-p;
		pl.second=upper_bound(p+1,p+m+1,cr[i])-p-1;
		if(pl.first<=pl.second && pl.first<=m){
			ans_car++;
			use_p[++cnt]=pl;
		}
	}
}
void sol2(){
	pii nowpi;
	nowpi.first=-1,nowpi.second=-1;
	sort(use_p+1,use_p+cnt+1);
	for(int i=1;i<=cnt;i++){
		if(nowpi.second<use_p[i].first){
			ans_p++;
			nowpi=use_p[i];
		}else{
			nowpi.first=max(nowpi.first,use_p[i].first);
			nowpi.second=min(nowpi.second,use_p[i].second);
		}
	}
	ans_p=m-ans_p;
}
//易发现:不超速很复杂,不好处理 
int main(){
	//freopen("detect.in","r",stdin);
	//freopen("detect.out", "w", stdout);
	cin>>T;
	while(T--){
		scanf("%d%d%d%d",&n,&m,&L,&V);
		memset(cl,-1,sizeof(cl));
		memset(cr,-1,sizeof(cr));
		memset(use_p,-1,sizeof(use_p));
		ans_car=n,ans_p=0,cnt=0;
		for(int i=1;i<=n;i++) scanf("%d%d%d",&d[i],&v[i],&a[i]);
		for(int i=1;i<=m;i++) scanf("%d",&p[i]);
		int pow;
		for(int i=1;i<=n;i++){
			if(v[i]<=V){
				if(a[i]<=0) continue;
				pow=v[i]*v[i]+2*a[i]*(L-d[i]);
				if(pow<=V*V) continue;//已经处理了会超速的加速 
			}//所有不超速区间都没有修改初始值-1; 
			if(a[i]>=0 && v[i]>V){
				cl[i]=d[i],cr[i]=L;
			}
			if(a[i]>0){
				cr[i]=L;
				pow=floor((V*V-v[i]*v[i])/(2.0*a[i]))+1;
				cl[i]=min(d[i]+pow,L);
			}
			if(a[i]<0){
				cl[i]=d[i];
				pow=ceil((V*V-v[i]*v[i])/(2.0*a[i]))-1;
				cr[i]=max(cl[i],pow+d[i]);
			}
		}
		sol1();
		sol2();
		cout<<ans_car<<" "<<ans_p<<"\n";
	}
	return 0;
} 
2024/10/31 19:14
加载中...