题目

三分法代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,q[N],a[N],b[N],mi=1e9;
inline int check(ll x){
    ll mi=1e9;
    for(int i=1;i<=n;++i){
        if(b[i]!=0)mi=min(mi,(q[i]-a[i]*x)/b[i]);
    }
    return x+mi;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>q[i]
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(a[i]!=0)mi=min(mi,q[i]/a[i]);
    }
    for(int i=1;i<=n;++i)cin>>b[i];
    ll l=0,r=mi;
    while(l<=r){
        ll lmid=l+(r-l)/3,rmid=r-(r-l)/3;
        if(check(lmid)>check(rmid))r=rmid-1;
        else l=lmid+1;
    }
    ll ans=1e9;
    for(int i=1;i<=n;++i){
        if(b[i]!=0)ans=min(ans,(q[i]-a[i]*r)/b[i]);
    }
    cout<<r+ans;
	return 0;
}