BZOJ 5106 [CodePlus2017]汀博尔

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题解】

二分答案。r要设好，不能随便设置为max(s,len)，不然check的时候会爆long long

 #include<cstdio>

 #include<algorithm>

 #define rg register

 #define N 200010

 #define LL long long

 using namespace std;

 LL n,s,len,mx,h[N],a[N],l,r,mid;

 inline LL read(){

     LL k=; char c=getchar();

     while(c<''||c>'')c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k;

 }

 inline bool check(){

     LL cnt=;

     for(rg int i=;i<=n;i++)

     if(1LL*h[i]+a[i]*mid>=len){

         cnt+=1LL*h[i]+a[i]*mid;

         if(cnt>=s) return ;

     }

     return ;

 }

 int main(){

     n=read(); s=read(); len=read();

     for(rg int i=;i<=n;i++) h[i]=read();

     for(rg int i=;i<=n;i++) a[i]=read(),mx=max(mx,a[i]);

     l=-; r=max(s,len)/mx+;

     while(l+<r){

         mid=(l+r)>>;

         if(check()) r=mid; else l=mid;

     }

     printf("%lld\n",r);

     return ;

 }