周赛Problem 1108: 蛋糕（二分答案）

周赛Problem 1108: 蛋糕（二分答案）

1108: 蛋糕

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 17   Solved: 4

Description

杨神打代码打得有点疲倦，于是他想要开始做蛋糕。若某一种蛋糕需要有n种材料，然后每种材料需要ai 克，杨神手里有每种材料bi克，而且因为杨神有多年积蓄的神奇粉末，每一克神奇粉末可以代替任何一种材料1克。然后他仙子啊纠结，自己的这些材料加上神奇粉末，最多可以做多少个蛋糕。就靠你们了。

Input

有多组数据不超过110组。
每组数据第一行输入两个整数，n,k(1 ≤ n ≤ 100 000, 1 ≤ k ≤ 1e9)--代表这个蛋糕需要n种材料,以及杨神有k克神奇粉末。
第二行有n个数a1, a2, ..., an (1 ≤ ai ≤ 1e9) 代表每种材料需要ai克。
第三行也是n个数b1, b2, ..., bn (1 ≤ bi ≤ 1e9)代表杨神现在拥有的材料。

Output

每组数据输出一个整数，代表最多能做多少个蛋糕。

Sample Input

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

Sample Output

2000000000
0

周赛的题目……本来完全没想法的，问了学长发现是智障了把n看成1e9了以为绝对不能暴力。一开始把判断合法函数写里面且忘记了是用ans记录答案而不是直接输出mid智障WA多次。写成check（）函数就好了，做的第一道二分答案的题目，还是有规律可循的。

代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
#define MMINF(x) memset(x,INF,sizeof(x))
const double PI=acos(-1.0);
const int N=100010;
using namespace std;
typedef long long LL;
LL n,k;
LL a[N],b[N];
bool check(LL mid,LL temp)
{for (int i=1; i<=n; i++){if(b[i]<mid*a[i]){if(mid*a[i]-b[i]<=temp)temp-=(mid*a[i]-b[i]);elsereturn false;;}}return true;
}
int main(void)
{ios::sync_with_stdio(false);int i,j;LL L,R;while (cin>>n>>k){for (i=1; i<=n; i++)cin>>a[i];for (i=1; i<=n; i++)cin>>b[i];L=0,R=2e9+9;LL mid,temp,ans;int flag;while (L<=R){temp=k;mid=(L+R)>>1;if(check(mid,temp)){ans=mid;L=mid+1;				}elseR=mid-1;	}cout<<ans<<endl;		}return 0;
}