题目
铁憨憨骑士团团长憨中憨有着特殊的能力来激发骑士的斗志——他会泡好喝的幽兰拿铁，一杯幽兰拿铁能激发一位骑士的斗志。
制作一杯拿铁需要 n 种原材料，每种原材料各需要 a1,a2,…,an 份，憨中憨现有每种原材料各 b1,b2,…,bn 份。
另外，他还有另外 m 份万能材料，每一份万能材料都能作为任意一种原材料的一份用于制作奶茶。
现在给你原材料和神秘材料的份数，求憨中憨最多能制作几杯幽兰拿铁。
题目链接
https://citel.bjtu.edu.cn/acm/problem/1923
输入数据
第一行为两个整数 n,m (1≤n≤10^5,0≤m≤10^7)，分别表示原材料的种类和万能材料的份数。
第二行为 n 个整数 a1,a2,…,an (1≤ai≤10^4)，ai 代表制作一杯奶茶需要第 i 种材料的份数。
第三行为 n 个整数 b1,b2,…,bn (1≤bi≤10^8)，bi 代表憨中憨拥有的第 i 种材料的份数。
输出数据
一个整数，表示憨中憨最多能制作奶茶的杯数。
样例输入
5 7
1 2 1 2 3
5 5 5 5 5
样例输出
3
样例说明
把 1 份万能材料当作第 2 种原材料，
把 1 份万能材料当作第 4 种原材料，
把 4 份万能材料当作第 5 种原材料，
共消耗万能材料 6 份，能制作 3 杯奶茶。
可以证明，剩余的材料不能制作更多奶茶。
问题分析
思路一
最多能制作几杯拿铁，是由（b[i] / a[i]）最小的那个原材料所决定的。我们只需要每次都把万能材料变成比例最小的那种材料即可。
但是一次应该投入多少原材料呢？一次只投放一份显然很慢。比较快的方法是使得比例最小的材料恰好超过第二小的材料。
具体策略如下：
1. 找出比例（b[i] / a[i]）最小的材料 A 和第二小的材料 B
2. 分配若干万能材料给 A, 使得 A 的比例（b[i] / a[i]）恰好大于 B 的比例
循环执行以上策略，直到万能材料全部用完，此时比例（b[i] / a[i]）的最小值就是问题的答案。
思路二（推荐）
对答案进行二分查找。
由数据范围易得，答案在0到2*10^8之间。
对边界取均值设为mid，验证是否可以制作出mid杯拿铁，如果是，说明答案大于等于mid；反之说明答案小于mid。根据验证结果更新边界，直到左边界大于右边界，退出循环，此时最后一个验证成功的值就是问题的答案。
核心代码如下：
while (ghbleft <= ghbright)
{
mid = ghbleft + (ghbright - ghbleft) / 2;
if (ok())
{
ans = mid;
ghbleft = mid + 1;
}
else
ghbright = mid - 1;
}
cout << ans << endl;
AC代码
思路一（1219 ms）
这个方法实际已经超时了，不过比赛的时候放宽了时间，所以也是可以AC的。
#include <bits/stdc++.h>
using namespace std;
int a[100005];
struct node
{
int i;
int x;
double num; //制作的数量
bool operator<(const node &s1) const
{
return num > s1.num;
}
} p;
priority_queue<node, vector<node> /**/> q;
int main()
{
int n, m, i;
cin >> n >> m;
for (i = 0; i < n; i++)
cin >> a[i];
for (i = 0; i < n; i++)
{
p.i = i;
cin >> p.x;
p.num = p.x * 1.0 / a[i];
q.push(p);
}
while (m > 0)
{
node fp = q.top();
q.pop();
int temp = q.top().num - fp.num;
temp = min(m, temp + 1);
fp.x += temp;
m -= temp;
fp.num = fp.x * 1.0 / a[fp.i];
q.push(fp);
}
node fp = q.top();
printf("%d\n", (int)fp.num);
return 0;
}
思路二（13 ms）
#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005];
int ghbleft = 0, ghbright = 2e8, mid, ans, n, m;
bool ok()
{
int t = m;
for (int i = 0; i < n; i++)
{
int num = a[i] * mid;
if (b[i] < num)
t -= num - b[i];
if (t < 0)
return false;
}
return true;
}
int main()
{
int i;
cin >> n >> m;
for (i = 0; i < n; i++)
cin >> a[i];
for (i = 0; i < n; i++)
cin >> b[i];
while (ghbleft <= ghbright)
{
mid = ghbleft + (ghbright - ghbleft) / 2;
if (ok())
{
ans = mid;
ghbleft = mid + 1;
}
else
ghbright = mid - 1;
}
cout << ans << endl;
return 0;
}