大样例都过了为什么会 0 分
查看原帖
大样例都过了为什么会 0 分
816310
CQ_Alice楼主2024/10/28 21:58
#include<bits/stdc++.h>
using namespace std ;
const int Max = 1e5 + 10 ; 
// 输入 
struct Node {
	double d , v , a ; 
} Car[Max] ;
int p[Max] ; 
int n , m ;
int T , L ;
double V ; 

// 瞬时速度 
double S_V( int i , double S ) {
	return sqrt( ( Car[i].v * Car[i].v ) + 2 * Car[i].a * ( S - Car[i].d ) ) ;
} 

// 二分
int Two_Val( int i ) {
	int l = 1 , r = m ; 
	while( l < r ) {
		int Mid = l + r >> 1 ; 
		if( Car[i].d <= p[Mid] ) r = Mid ; 
		else l = Mid + 1 ; 
	}
	if( Car[i].d <= p[l] ) return l ; 
	else return -1 ;
}
int Two( int i , int Val ) {
	int l = Val , r = m ; 
	if( l > r ) return -1 ; 
	int Mid ; 
	while( l < r ) {
		if( Car[i].a >= 0 ) {
			Mid = l + r >> 1 ;
			if( S_V( i , p[Mid] ) <= V ) l = Mid + 1 ; 
			else r = Mid ; 
		} else {
			Mid = l + r + 1 >> 1 ; 
			if( S_V( i , p[Mid] ) > V ) l = Mid ; 
			else r = Mid - 1 ;  
		}
	}
	if( S_V( i , p[l] ) > V ) return l ;
	else return -1 ;  
}
 
// 超速区间
struct Sert {
	int l , r ; 
	bool operator < ( const Sert &A ) const {
		return A.r > r ; 
	}
} Tr[Max] , Qr[Max] ; // Qr 优化后的 
bool Rule( Sert A , Sert B ) {
	if( A.l == B.l ) return A.r > B.r ; 
	else return A.l < B.l ; 
}
priority_queue < Sert > Que ;
int Ans , Nul ;  
int Rigth ; 
int Cnt ; // 超速数量 

void Solve( ) {
	scanf("%d%d%d%lf" , &n , &m , &L , &V ) ; 
	for(int i = 1 ; i <= n ; i ++ ) {
		scanf("%lf%lf%lf" , &Car[i].d , &Car[i].v , &Car[i].a ) ; 
	}
	for(int i = 1 ; i <= m ; i ++ ) scanf("%d" , &p[i] ) ; 
	Cnt = 0 ; 
	for(int i = 1 , Val , Key ; i <= n ; i ++ ) {
		Val = Two_Val( i ) ; 
		Key = Two( i , Val ) ; 
		if( Key != -1 ) {
			if( Car[i].a >= 0 ) Tr[ ++ Cnt ] = ( Sert ) { Key , n } ;
			else Tr[ ++ Cnt ] = ( Sert ) { Val , Key } ;
		} 
	}
	
	// 贪心
	sort( Tr + 1 , Tr + Cnt + 1 , Rule ) ; 
	for(int i = 1 ; i <= Cnt ; i ++ ) {
		while( !Que.empty( ) && Tr[i].r < Que.top( ).r ) Que.pop( ) ;
		Que.push( ( Sert ) { Tr[i].l , Tr[i].r } ) ;
	} 
	Nul = Ans = Rigth = 0 ;
	while( !Que.empty( ) ) Qr[ ++ Nul ] = Que.top( ) , Que.pop( ) ; 
	sort( Qr + 1 , Qr + Nul + 1 , Rule ) ; 
	for(int i = 1 ; i <= Nul ; i ++ ) {
		if( Qr[i].l > Rigth ) Ans ++ , Rigth = Qr[i].r ; 
	}
	printf("%d %d\n" , Cnt , m - Ans ) ;
}

int main( ) {
	scanf("%d" , &T ) ; 
	while( T -- ) Solve( ) ; 
	return false ; 
}

很普通的思路,因为超速被检测的仪器会形成一个区间,所以可以考虑先二分求出区间,再贪心一下。

主要是大样例都过了为什么会一分没有

2024/10/28 21:58
加载中...