题目描述
大学期间的某一天,大T 得知,某位同学家里是做养殖场的,养殖场中有 N 种不同的畜禽,每种有 Xi 只/匹,现在为了这位同学交学费,决定卖出一部分畜禽。
卖出畜禽时,大家决定采取“雨露均沾”的模式卖出:若一种畜禽卖出了 k 只,那么其他种类的畜禽都要卖出 k 只,若不足 k 只的,则全部卖出。
现给定总学费 M 元,及每种畜禽卖出的价格 Yi 元,求出 k 最少为多少时,才能满足学费要求,题目保证可以满足学费要求。
输入
输入第一行两个整数 N,M,表示畜禽种类数。(1 <= N <= 10^5,2 <= M <= 10^9)
接下来一行输入 N 个数字,表示 Xi。(1 <= Xi <= 10^5)
再接下来一行输入 N 个数字,表示 Yi。(1 <= Y_i <= 10^2)
输出
输出一行一个整数,表示每种家禽的最少卖出数。
题目限制
时间限制:C/C++语言 1000MS;其他语言 3000 MS 内存限制:C/C++语言 262144KB;其他语言 786432KB
样例输入
5 30
3 3 1 3 3
4 3 9 1 5
样例输出
xxxxxxxxxx
2
x
using namespace std;
int main() {
ios::sync_with_stdio(false);
long long x[100005], y[100005];
int n, m, l = 1, r = 1e5;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> x[i];
for (int i = 1; i <= n; i++) cin >> y[i];
while (l < r) {
long long mid = (l + r) >> 1;
long long ans = 0;
for (int i = 1; i <= n; i++) {
if (x[i] > mid) ans += mid * y[i];
else ans += x[i] * y[i];
}
if (ans >= m) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}