求助,每次都误差1(悬棺)
查看原帖
求助,每次都误差1(悬棺)
1242018
aleavf楼主2024/11/28 19:26
#include<bits/stdc++.h>
using namespace std;
const int N=100000;
struct node{
	int d,v,a,q;
}s[N];
struct zuoyou{
	int le,ri;
}c[N];
int t;
bool cmp(zuoyou aa,zuoyou bb){
	return aa.ri<bb.ri;
}
int p[N];
int main() {
	scanf("%d",&t);
	while(t--){
		memset(p,0,sizeof p);
		memset(c,0,sizeof c);
		memset(s,0,sizeof s);
		int n,m,V,l,ans=0,ans1=1,you=0;
		scanf("%d%d%d%d",&n,&m,&l,&V);
		for(int i = 1;i<=n;++i)
			scanf("%d%d%d",&s[i].d,&s[i].v,&s[i].a);
		for(int i = 1;i<=m;++i)	cin>>p[i];
		for(int i = 1;i<=n;++i){
			int y=(1.0*V*V-1.0*s[i].v*s[i].v)/(1.0*2*s[i].a)+s[i].d;
			int L=1,R=m,mid;
			if(s[i].a>=0){
				if(s[i].a==0&&s[i].v<=V) continue;
				if(y>=p[m])continue;
				int mid=lower_bound(p+1,p+1+m,s[i].d) - p;
				L=mid;
				while(L<R){
					mid=(L+R)/2;
					if(p[mid]<y) L=mid+1;
					else R=mid;
				}
				ans++;
				c[ans].le=L,c[ans].ri=m;
			}
			else{
				if(y<=s[i].d) continue;
				if(s[i].v<=V) continue;
				int mid=lower_bound(p+1,p+1+m,s[i].d) - p;
				if(p[mid]<y)ans++;
				else continue;
				int w=mid;
				L=mid,R=m;
				while(L<R){
					mid=(L+R)/2;
					if(V*V<s[i].v*s[i].v+2*s[i].a*(p[mid]-s[i].d)) L=mid+1;
					else R=mid;
				}
				c[ans].le=w,c[ans].ri=mid;
			}
		}
		sort(c+1,c+1+ans,cmp);
		you=c[1].ri;
		for(int j = 2;j<=ans;j++){
			if(you<c[j].le){
				ans1++;
				you=c[j].ri;
			}
		}
		cout<<ans<<' '<<m-ans1<<endl;;
	}
}
2024/11/28 19:26
加载中...