Magic Powder - 2（二分）

Dear 丶 2022-06-05 01:10 128阅读 0赞

D2. Magic Powder - 2

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The term of this problem is the same as the previous one, the only exception — increased restrictions.

Input

The first line contains two positive integers *n* and *k* (1 ≤ *n* ≤ 100 000, 1 ≤ *k* ≤ 109) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109), where the *i*\-th number is equal to the number of grams of the *i*\-th ingredient, needed to bake one cookie.

The third line contains the sequence *b*1, *b*2, ..., *b**n* (1 ≤ *b**i* ≤ 109), where the *i*\-th number is equal to the number of grams of the *i*\-th ingredient, which Apollinaria has.

Output

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.

Examples

input

1 1000000000
    1
    1000000000

output

2000000000

input

10 1
    1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
    1 1 1 1 1 1 1 1 1 1

output

input

3 1
    2 1 4
    11 3 16

output

input

4 3
    4 3 5 6
    11 12 14 20

output

思路：又是栽倒了二分手里，二分优化时间。饼干数量的范围是0~2e9， 所以二分选择适合的最大的饼干数量就可以。

#include<cstdio>
    #include<iostream>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    ll have[maxn], need[maxn];
    
    int main(){
        int n, k;
        scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++)
            scanf("%lld", need+i);
        for(int i=1; i<=n; i++)
            scanf("%lld", have+i);
        ll l=0, r=2e9;// long ong 类型 否则超数据。
        ll mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            ll s=k, flag=0;
            for(int i=1; i<=n; i++)
            {
                if(mid*need[i]>have[i])
                {
                    s-=(mid*need[i]-have[i]);//看是否能制作mid数量的饼干；
                    if(s<0)
                    {
                        flag=1; break;
                    }
                }
            }
            if(flag)
                r=mid-1;
            else
                l=mid+1;
        }
        printf("%lld\n", r);//二分终止的条件一定是l==r==答案，然后l=mid+1，所以答案；
        return 0;
    }