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 () ;
}
虽然感觉这个判定条件比较宽松但是也过了。