关于一个我同学想的玄学东西
查看原帖
关于一个我同学想的玄学东西
895690
gghack_Nythix楼主2025/7/3 20:29

rt,这个对吗。

# include <bits/stdc++.h>
# define dl double
# define ppb pop_back
# define ppf pop_front
# define psb push_back
using namespace std;
const int N = 5e5 + 5 ;
int n , m ;
dl c[2][N] , cl[N] , cr[N] , k ;
static inline bool check ( dl x ) {
	for ( int i = 1;i <= m;++i ) {
		cl[i] = ceil ( c[0][i] / x ) - 1 ;
		cr[i] = ceil ( c[1][i] / x ) - 1 ;
	}
	deque < int > ql , qr ;
	for ( int i = 1;i <= m;++i ) {
		while ( !ql.empty() && cl[ ql.back() ] <= cl[i] ) ql.ppb(); ql.psb ( i ) ;
		while ( !ql.empty() && i - ql.front() > (int) k ) ql.ppf() ;
		while ( !qr.empty() && cr[ qr.back() ] <= cr[i] ) qr.ppb(); qr.psb ( i ) ;
		while ( !qr.empty() && i - qr.front() > (int) k ) qr.ppf() ;
		if ( cl[ ql.front() ] + cr[ qr.front() ] > n ) return 0 ;
	}
	return 1;
}
void solve () {
	cin >> n >> m >> k;
	for ( int i = 1;i <= m;++i ) cin >> c[0][i] ; 
	for ( int i = 1;i <= m;++i ) cin >> c[1][i] ; 
	dl l = 0.0 , r = 5e5 ; 
	while ( r - l > 1e-8 ) {
		dl mid = ( l + r ) / 2.00;
		if ( check ( mid ) ) r = mid ; 
		else l = mid ;
	}
	return cout << fixed << setprecision(6) << l << '\n' , void();
}
signed main () {
	ios::sync_with_stdio ( false ) , cin.tie( 0 ) , cout.tie( 0 ) ;
	int T ; cin >> T ; while ( T-->0 ) solve () ;
}

虽然感觉这个判定条件比较宽松但是也过了。

2025/7/3 20:29
加载中...