家里养羊-二分答案

题目

题目描述

大学期间的某一天，大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

样例输出

2

思路

• 思路简单，单纯的二分答案套路

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

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;
}