C++ 金币获取 求解 二分答案

Question

3.金币获取
题目描述
XZH 有一种研究，那就是机器。
他研究并发明了 n 台机器，用 1∼n 标号。每台机器有两个属性。对于第 i 台机器，
有 ai ,bi 两个属性，解释见下文。
现在，XZH 要把自己的银币换成金币，他的做法是将这些银币依次使用这 n 台机器。如果
他要使 x 枚银币通过第 i 台机器，那么会发生下面的事情。
 如果 x≤ai ，则银币数清空，不会获得新的金币。
 如果 x>ai ，则银币数会减少 ai ，当银币数 x=x−ai 之后，XZH 会获得 x×bi 枚
金币。
举个例子。
XZH 有 9 枚银币，他要通过 (a1 ,b1 )=(5,3),(a2 ,b2 )=(10,10) 的两台机器
对于第一台机器，由于 9>5，所以这些银币可以通过这一台机器，并且剩下 4 枚银币。所
以他获得了 4×3=12 枚金币。
对于第二台机器，由于他只有 4 枚银币，4≤10，所以他的所有银币会被第二台机器消耗掉，
不会获得金币。
综上所述，他会获得 12 枚金币。
现在，他想知道，如果他想用这 n 台机器获得至少 k 枚金币，他至少需要多少枚银币？
本题采用多组数据。
输入格式
第一行，输入一个整数 T，下面有 T 组数据。
对于每一组数据：
第一行一个整数 n,k。
第二行，n 个整数，第 i 个表示 ai 。
第三行，n 个整数，第 i 个表示 bi 。
输出格式
对于每一组数据，输出一个 ans，用换行隔开，代表 XZH 获得至少 k 枚金币需要银币数量
的最小值。
样例
样例输入 1 样例输出 1
2 9 7
2 12
5 10
3 10
2 12
4 2
3 4
样例说明
样例 1 解释：XZH 开始有 9 枚银币。
通过第一个机器 (5,3)，他剩余 4 枚银币，获得 4×3=12 枚金币。
由于 4≤10，所以通过第二台机器的时候不会产生收益。
所以，他有 9 枚金币。
提示
对于 50% 的数据 1≤n≤1000，1≤k≤1000
对于 100% 的数据 1≤T≤10,1≤n≤104,1≤k≤109,0≤ai ≤109,0≤bi ≤10,bi >0。

c++求解

Answer 1

该回答引用自GPT-3.5, 由博主 GISer Liu 编写：

好的，我们来详细分析并解决这个问题。

问题分析

XZH 有 n 台机器，每台机器有两个属性 (a_i) 和 (b_i)。他希望通过这些机器将银币转换成金币。具体规则如下：

• 如果银币数 (x \leq a_i)，则银币数清空，不会获得新的金币。
• 如果银币数 (x > a_i)，则银币数会减少 (a_i)，并且获得 ((x - a_i) \times b_i) 枚金币。

XZH 想知道，如果他想用这 n 台机器获得至少 k 枚金币，他至少需要多少枚银币。

解决思路

我们可以使用二分答案的方法来解决这个问题。具体步骤如下：

1. 定义二分搜索的范围：银币的数量范围可以从 0 到 (10^9 \times 10^4)（因为 (a_i) 的最大值是 (10^9)，且最多有 (10^4) 台机器）。
2. 检查函数：编写一个函数 check(mid, n, a, b, k) 来检查如果使用 mid 枚银币是否可以获得至少 k 枚金币。
3. 二分搜索：在定义的范围内进行二分搜索，找到最小的银币数量 mid，使得 check(mid, n, a, b, k) 返回 true。

代码实现

下面是详细的代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 检查函数，判断使用 mid 枚银币是否可以获得至少 k 枚金币
bool check(long long mid, int n, vector<int>& a, vector<int>& b, long long k) {
    long long gold = 0;
    for (int i = 0; i < n; ++i) {
        if (mid > a[i]) {
            gold += (mid - a[i]) * b[i];
        }
    }
    return gold >= k;
}

// 二分答案函数
long long binary_search(int n, vector<int>& a, vector<int>& b, long long k) {
    long long left = 0, right = 1e14; // 1e14 是银币数量的上限
    long long ans = 0;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (check(mid, n, a, b, k)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        long long k;
        cin >> n >> k;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
        }
        long long result = binary_search(n, a, b, k);
        cout << result << endl;
    }
    return 0;
}

代码解释

1. check 函数：

   • 输入参数：mid（当前尝试的银币数量），n（机器数量），a 和 b（机器属性数组），k（目标金币数量）。
   • 计算使用 mid 枚银币通过所有机器后能获得的总金币数量。
   • 返回是否满足至少获得 k 枚金币的条件。

2. binary_search 函数：

   • 使用二分搜索在可能的银币数量范围内查找最小的银币数量，使得通过所有机器后能获得至少 k 枚金币。

3. main 函数：

   • 读取输入数据，对每一组数据调用 binary_search 函数，并输出结果。

总结

通过上述分析和代码实现，我们可以有效地解决这个问题。使用二分答案的方法可以在合理的时间内找到最小的银币数量，满足获得至少 k 枚金币的条件。希望这个解答对您有所帮助！

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑