当前位置 : 主页 > 网页制作 > HTTP/TCP >

D2. Magic Powder - 2

来源:互联网 收集:自由互联 发布时间:2021-06-16
题目链接:http://codeforces.com/contest/670/problem/D2 题意: 你的蛋糕需要n个原材料,你现在有k个魔法材料,魔法材料可以转化为任何材料 现在告诉你蛋糕每个材料需要多少,以及你现在有多

题目链接:http://codeforces.com/contest/670/problem/D2

 

题意:

你的蛋糕需要n个原材料,你现在有k个魔法材料,魔法材料可以转化为任何材料

现在告诉你蛋糕每个材料需要多少,以及你现在有多少个

问你最多能够做出多少个蛋糕来

 

思路:

直接二分就好了,注意加起来会爆int

以及r给到2e9才行

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+7;
 4 long long a[maxn],b[maxn],k;
 5 int n;
 6 bool check(long long x)
 7 {
 8     long long ans = 0;
 9     for(int i=1;i<=n;i++)
10         if(a[i]*x-b[i]>k)return false;
11     for(int i=1;i<=n;i++)
12         ans+=max(a[i]*x-b[i],0LL);
13     if(ans<=k)return true;
14     return false;
15 }
16 int main()
17 {
18     scanf("%d%lld",&n,&k);
19     for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
20     for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
21     long long l=0,r=2e9,ans=0;
22     while(l<=r)
23     {
24         int mid=(l+r)/2;
25         if(check(mid))l=mid+1,ans=mid;
26         else r=mid-1;
27     }
28     cout<<ans<<endl;
29 }
网友评论