Magic Powder - 1，2

问题

This problem is given in two versions that differ only by constraints. If you can solve this problem in large constraints, then you can just write a single solution to the both versions. If you find the problem too difficult in large constraints, you can write solution to the simplified version only.

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value ai — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.

Apollinaria has bi gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.

Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder.

输入 

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

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), 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 ≤ 1000), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.

输出 

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

Sample 1

Inputcopy	Outputcopy
3 1 2 1 4 11 3 16	4

Sample 2

Inputcopy	Outputcopy
4 3 4 3 5 6 11 12 14 20	3

Note

In the first sample it is profitably for Apollinaria to make the existing 1 gram of her magic powder to ingredient with the index 2, then Apollinaria will be able to bake 4 cookies.

In the second sample Apollinaria should turn 1 gram of magic powder to ingredient with the index 1 and 1 gram of magic powder to ingredient with the index 3. Then Apollinaria will be able to bake 3 cookies. The remaining 1 gram of the magic powder can be left, because it can't be used to increase the answer.

解题思路 ：

做一块饼干需要n种材料，k个魔法材料，

ai为每种材料的克数

bi为现有每种材料的总数，魔法材料可以代替任何一种材料，问最大能做多少。

二分思想：最多能做多少个，从比题目给的范围大的范围里二分，比如左边0，右边10000，从这个区间内开始二分。比方做一个所用到材料数乘以n的结果，小于等于我们所现有的总材料了，这n个才能做出来，如果大于我们所拥有的材料总数，说明我们的材料不够，需要从k个魔法材料里面拿，如果魔法材料被拿完了，变成负数，就意味着这n个做不成，然后缩小n的范围，否则就增大n的范围

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

int n,m;
int g[1010],k[1010],p[1010];

int check(int x)
{
 int res=0;
 for(int i=0; i<n; i++)
 {
  p[i]=k[i]-x*g[i];
  if(p[i]<0) 
  res-=p[i];
 }
 if(res<=m) 
 return 1;
 else 
 return 0;
}

int main()
{
 cin>>n>>m;
 for(int i=0; i<n; i++) cin>>g[i];
 for(int i=0; i<n; i++) cin>>k[i];
 int l=0,r=10000;
 while(l<r)
 {
  int mid=(l+r+1)>>1;
  if(check(mid)) l=mid;
  else r=mid-1;
 }
 cout<<l;
 return 0;
}

输入

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.

输出

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

Sample 1

Inputcopy	Outputcopy
1 1000000000 1 1000000000	2000000000

Sample 2

Inputcopy	Outputcopy
10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 1 1 1 1 1 1 1 1	0

Sample 3

Inputcopy	Outputcopy
3 1 2 1 4 11 3 16	4

Sample 4

Inputcopy	Outputcopy
4 3 4 3 5 6 11 12 14 20	3

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctype.h>
using namespace std;
typedef long long ll;


ll n,m;
ll g[100010],k[100010],p[100010];

ll check(ll x)
{
 ll res=0;
 for(ll i=0; i<n; i++)
 {
  if(g[i]*x>k[i]) 
  res=res+g[i]*x-k[i];
  if(res>m) 
  return 0;
 }
 return 1;
}

int main()
{
 cin>>n>>m;
 for(int i=0; i<n; i++) cin>>g[i];
 for(int i=0; i<n; i++) cin>>k[i];
 ll l=0,r=2000000000;
 while(l<r)
 {
  ll mid=(l+r+1)>>1;
  if(check(mid)) l=mid;
  else r=mid-1;
 }
 cout<<l;
 return 0;
}

和前面那个一样，注意数据范围，还有check函数里if判断条件不能像第一个那样写，数据太大，乘法和减法一块会容易出错，最好像第二个代码那样写