50分 WA on#1#2#7#9#10
查看原帖
50分 WA on#1#2#7#9#10
427590
SHENTONG_ZY楼主2024/11/1 14:13
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int T,n,m,L,V,d[N],v[N],a[N],l[N],r[N],p[N];
struct qj{int l,r;}q[N];
bool cmp(qj x,qj y){
	return x.r<y.r;
}
bool zs(double x){//判断整数
	int xz=x;
	if(xz==x) return true;
	return false;
}
double js1(int v,int a){//加速时的计算
	double t=(V-v)*1.0/a;
	double s=v*t+0.5*a*t*t;
	return s;
}
double js2(int v,int a){//减速时的计算
	double t=(v-V)*1.0/abs(a);
	double s=v*t+0.5*a*t*t;
	return s;
}
int fd(int x){
	int l=0,r=m+1;
	while(l+1<r){
		int mid=(l+r)/2;
		if(p[mid]>=x) r=mid;
		else l=mid;  
	}
	return r;
}
pair<int,int> work(int d,int v,int a){//预处理超速区间
	int l,r;
	if(a==0){
		if(v>V) l=d,r=L;
		else l=-1,r=-1; 
	}
	if(a>0){
		if(v>V) l=d,r=L;
		if(v==V) l=d+1,r=L;
		if(v<V){
			double ds=js1(v,a);
			if(zs(ds)){
				if(d+ds+1<=L) l=d+ds+1,r=L;
				else l=-1,r=-1;
			}
			else{
				if(d+ceil(ds)<=L) l=d+ceil(ds),r=L;
				else l=-1,r=-1;
			}
		}
	}
	if(a<0){
		if(v<=V) l=-1,r=-1;
		else{
			double ds=js2(v,a);
			if(zs(ds)) l=d,r=min(int(d+ds-1),L);
			else l=d,r=min(int(ds+d),L);
		}
	}
	return make_pair(l,r);
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m>>L>>V;
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&d[i],&v[i],&a[i]);
			l[i]=work(d[i],v[i],a[i]).first,r[i]=work(d[i],v[i],a[i]).second;
		}
		for(int i=1;i<=m;i++) scanf("%d",&p[i]);
		int s=0;
		for(int i=1;i<=n;i++){
			if(l[i]==-1) continue;
			if(a[i]>=0){
				if(l[i]<=p[m]){//开始超速的地方小于等于最后一个测速仪
					q[++s].l=l[i];
					q[s].r=r[i];
				}
			}
			else{
				int k=fd(l[i]);
				if(p[k]<=r[i]){//第一个大于等于l[i]的测速仪小于r[i]
					q[++s].l=l[i];
					q[s].r=r[i];
				}
			}
		}
		printf("%d ",s);
		sort(q+1,q+1+s,cmp);
		int pi=1,ci=1,ans=0;
		while(1){
			if(p[pi]>=q[ci].l&&p[pi]<=q[ci].r&&(p[pi+1]>q[ci].r||pi==m)){
				ans++;
				while(p[pi]>=q[ci].l&&p[pi]<=q[ci].r&&ci<=s) ci++;
			}
			else pi++;
			if(ci>s||pi>m) break;
		}
		printf("%d\n",m-ans);
	}
	
	
	return 0;
}

大样例中第一个答案有时候会大1

2024/11/1 14:13
加载中...