40分球条
查看原帖
40分球条
922019
xiaoniu142857楼主2024/11/2 15:44
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 100000
#define rep(i,a,b) for(int i(a);i<(b);++i)
using namespace std;
struct Range
{
    int l,r;
    inline bool operator<(const Range &rhs) const
    {
    	return r==rhs.r?l<rhs.l:r<rhs.r;
	}
}r[N];
int d[N],v[N],a[N],p[N],rl,cnt;
inline void add_range(int a,int b)
{
	if(a<=b)
	{
		r[rl++]={a,b};
		++cnt;
	}
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T,n,m,l,vx,cur,ans;
    cin>>T;
    while(T--)
    {
    	// 初始化&输入 
        rl=cnt=0;
        cin>>n>>m>>l>>vx;
        rep(i,0,n) cin>>d[i]>>v[i]>>a[i];
        rep(i,0,m) cin>>p[i];
        
        // 判定超速区间 
        rep(i,0,n)
        {
            if(a[i]==0)
            {
                if(v[i]>vx)
                {
                    add_range(lower_bound(p,p+m,d[i])-p,m-1);
            	}
				continue;
            }
            double dis=d[i]+0.5*(vx*vx-v[i]*v[i])/a[i];
            if(dis>=d[i])
            {
				if(a[i]<0)
				{
					add_range(lower_bound(p,p+m,d[i])-p,lower_bound(p,p+m,dis)-p-1);
				}
				else
				{
					add_range(upper_bound(p,p+m,dis)-p,m-1);
				}
            }
        }
        
        // 贪心 
        sort(r,r+rl);
        cur=r[0].r,ans=m-1;
        rep(i,1,rl)
        {
        	if(cur<r[i].l)
        	{
        		cur=r[i].r;
        		--ans;
			}
		}
        cout<<cnt<<' '<<ans<<'\n';
    }
    return 0;
}
2024/11/2 15:44
加载中...