当前位置: 首页 > 工具软件 > POWDER > 使用案例 >

Codeforces 670D2 Magic Powder - 2【二分】

商同化
2023-12-01

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 a1, a2, ..., an (1 ≤ ai ≤ 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 b1, b2, ..., bn (1 ≤ bi ≤ 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
0
Input
3 1
2 1 4
11 3 16
Output
4
Input
4 3
4 3 5 6
11 12 14 20
Output
3

题目大意:

给你N种材料,以及M个魔法材料。

每个魔法材料可以变成任意一种魔法材料。

现在已知做一个饼干要用每种材料Ai个,而且已知每种饼干我们初始有Bi个。

问最多可以做出来多少饼干。


思路:


明显如果我们能够做出来x个饼干,那么一定能够做出来x-1个饼干,同理x-2也一定能够做出来。

所以这里一定有一个单调性在这里边。

那么我们二分结果,然后check一下就行。

注意数据范围。


Ac代码:

#include<stdio.h>
#include<string.h>
using namespace std;
#define ll __int64
ll n,m;
ll a[150000];
ll b[150000];
ll Slove(ll mid)
{
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        if(b[i]-a[i]*mid<0)sum+=b[i]-a[i]*mid;
        if(-sum>m)return 0;
    }
    if(sum>=0)return 1;
    if(sum<0&&-sum<=m)return 1;
    return 0;
}
int main()
{
    while(~scanf("%I64d%I64d",&n,&m))
    {
        for(ll i=0;i<n;i++)scanf("%I64d",&a[i]);
        for(ll i=0;i<n;i++)scanf("%I64d",&b[i]);
        ll ans=0;
        ll l=0;
        ll r=2000000000;
        while(r-l>=0)
        {
            ll mid=(l+r)/2;
            if(Slove(mid)==1)
            {
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        printf("%I64d\n",ans);
    }
}









 类似资料: