50pts求调
查看原帖
50pts求调
669924
guozhetao楼主2024/10/27 20:46

rt,考场代码,过了所有大样例,求助。

#include<bits/stdc++.h>
using namespace std;
long long T;
long long n,m;//车辆 测速仪数量 
double l,V;//主干道长度、主干道限速 
double d[100005],v[100005],a[100005];//车驶入位置,初始速度、加速度
double dis[100005];//测速仪位置 
struct node {
	int le,ri;//左右端点 
	friend bool operator <(node x,node y) {
		return x.ri < y.ri;
	}
}ed[100005];
int main() {
	scanf("%lld",&T);
	while(T--) {
		long long ans1 = 0;
		scanf("%lld %lld %lf %lf",&n,&m,&l,&V);
		for(int i = 1;i <= n;i++) scanf("%lf %lf %lf",&d[i],&v[i],&a[i]);
		for(int i = 1;i <= m;i++) scanf("%lf",&dis[i]);
		//超速车辆 
		for(int i = 1;i <= n;i++) {
			if(a[i] > 0) {
				if(dis[m] >= d[i]) {
					if(v[i] * v[i] + 2.0 * a[i] * (dis[m] - d[i]) > V * V)  {
						ans1++;
						int l = 1,r = m,mid;
						while(l < r) {
							mid = (l + r) >> 1;
							if(dis[mid] >= d[i] and v[i] * v[i] + 2.0 * a[i] * (dis[m] - d[i]) > V * V) r = mid;
							else l = mid + 1;
						}
						ed[ans1].le = l,ed[ans1].ri = m;
					}
				}
			}
			else if(a[i] == 0) {
				if(dis[m] >= d[i] and v[i] > V) {
					ans1++;
					int l = 1,r = m,mid;
					while(l < r) {
						mid = (l + r) >> 1;
						if(dis[mid] >= d[i]) r = mid;
						else l = mid + 1;
					}
					ed[ans1].le = l,ed[ans1].ri = m;
				}
			}
			else {
				int l = 1,r = m,mid;
				while(l < r) {
					mid = (l + r) >> 1;
					if(dis[mid] >= d[i]) r = mid;
					else l = mid + 1;
				}
				if(v[i] * v[i] + 2.0 * a[i] * (dis[l] - d[i]) > V * V) {
					ans1++,ed[ans1].le = l,r = m; 
					while(l < r) {
						mid = (l + r + 1) >> 1;
						if(dis[mid] >= d[i] and v[i] * v[i] + 2.0 * a[i] * (dis[mid] - d[i]) > V * V) l = mid;
						else r = mid - 1;
					}
					ed[ans1].ri = l;
				}
			}
			//printf("%lld %lld\n",i,ans1);
		}
		//
		sort(ed + 1,ed + ans1 + 1);
		long long ans2 = 0;
		//for(int i = 1;i <= ans1;i++)printf("__________%lld %lld\n",ed[i].le,ed[i].ri);
		for(int i = 1,j = 0;i <= ans1;i++) {
			if(ed[i].le > ed[j].ri) {
				ans2++,j = i;
			}
		}
		printf("%lld %lld\n",ans1,m - ans2);
	}
	return 0;
}

2024/10/27 20:46
加载中...