USACO銀牌題目 TheMeetingPlaceCannotBeChanged(二分查找) 樣例代碼
#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXF=6e4;
vector<int> x(MAXF+1),v(MAXF+1);
? ? ? ??
bool is_larger_eq_min(double m){
? ? //最大的起點(diǎn)小于等于最小終點(diǎn)=>存在地點(diǎn)所有客人都能到=>m大于等于最小時(shí)間
? ? double maxa=x[1]-m*v[1];
? ? double minb=x[1]+m*v[1];
? ? for(int i=2;i<=n;i++){
? ? ? ? maxa=max(x[i]-m*v[i],maxa);
? ? ? ? minb=min(x[i]+m*v[i],minb);
? ? ? ? if(maxa>minb){
? ? ? ? ? ? return false;
? ? ? ? }
? ? }
? ? return true;
}? ??
? ? ? ??
int main()
{
? ? cin>>n;
? ? for(int i=1;i<=n;i++){
? ? ? ? cin>>x[i];
? ? }? ??
? ? for(int i=1;i<=n;i++){
? ? ? ? cin>>v[i];
? ? }
? ? double l=0, r=1e9+1;
? ? while(r-l>1e-7){
? ? ? ? double m=(r+l)/2;
? ? ? ? if(is_larger_eq_min(m)){
? ? ? ? ? ? r=m;
? ? ? ? }else{
? ? ? ? ? ? l=m;
? ? ? ? }? ??
? ? }??
? ? cout<<setprecision(8)<<r<<endl;//必須設(shè)置,否則輸出精度可能不夠題目要求
? ? return 0;
}