80分求调 悬关
查看原帖
80分求调 悬关
849627
MarcLian楼主2025/8/31 09:12

RT.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+9;
const double eps=1e-9; 
struct Car{
	ll d,v,a;
}vh[N];
ll p[N],L[N],R[N];
pair<ll,ll> range[N];
int main(){
	ll t;
	cin>>t;
	while(t--){
		memset(L,0,sizeof(L));
		memset(R,0,sizeof(R));
		memset(p,0,sizeof(p));
		memset(vh,0,sizeof(vh));
		memset(range,0,sizeof(range)); // 多组数据清空 
		ll n,m,l,V,nRng=0;
		cin>>n>>m>>l>>V;
		for(ll i = 1;i <= n;i++){
			cin>>vh[i].d>>vh[i].v>>vh[i].a;
		}
		for(ll i = 1;i <= m;i++)cin>>p[i];
		sort(p+1,p+m+1);
		
		for(ll i = 1;i <= n;i++){// 对于每个车计算其简化版超速区间(即原超速区间所包含的测速仪区间)为了排除有超速但区间内没有测速仪的情况 
			ll d=vh[i].d,v=vh[i].v,a=vh[i].a;
			double exc=(double)(V*V-v*v)/a/2+d;
			ll left=-1,right=-2;// 此为简化版超速区间左右端点 
			if(a==0){// 分类讨论加速度 
				if(v>V){
					left=lower_bound(p+1,p+m+1,d)-p;
					right=m;
				}
			}
			else if(a<0){
				if(l<exc-eps)exc=l;// 精度处理 
				if(v>V){
					left=lower_bound(p+1,p+m+1,d)-p;
					right=lower_bound(p+1,p+m+1,exc-eps)-p-1;
				}
			}
			else{
				if(v>V){
					left=lower_bound(p+1,p+m+1,d)-p;
					right=m; 
				}
				else if(exc<l-eps){// 精度处理 
					left=upper_bound(p+1,p+m+1,exc+eps)-p; 
					right=m;
				}
			}// 只保留有效区间 
			if(left<=right)range[++nRng]=make_pair(right,left);// 为了按右端点排序,将右端点作为第一关键字  
		}
		sort(range+1,range+1+nRng);
		for(ll i = 1;i <= nRng;i++){// 排序后存储左右端点 
			L[i]=range[i].second;
			R[i]=range[i].first;
		}
		ll lastR=-1,ans=0;
		for(ll i = 1;i <= nRng;i++){// 贪心选择测速仪,选择第一个没有被覆盖的超速区间安装一个测速仪 
			if(L[i]>lastR){
				lastR=R[i];
				ans++;
			}
		}
		cout<<nRng<<" "<<m-ans<<'\n';
		// 最后求的是最多关闭的测速仪数量 
	}
	return 0;
}
2025/8/31 09:12
加载中...