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

Question

C++ 金币获取 求解 二分答案
c++
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
2
2 12
5 10
3 10
2 12
4 2
3 4
样例输出 1
9 7
样例说明
样例 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

为了解决这个问题，我们需要理解如何通过给定的机器以最少的银币数量获得至少 k 枚金币。关键在于确定每一台机器对最终金币数量的贡献，以及如何在满足条件的情况下最小化银币的使用。

考虑到 bi 的范围在 [0, 10] 之间，且 bi > 0，我们可以观察到，当银币数量足够多时，通过某台机器获得的金币数量将随银币数量的增加而线性增加（但有一个 ai 的门槛）。

我们可以采用二分搜索的方法来确定最小的银币数量。对于给定的银币数量 mid，我们可以模拟使用这些银币通过所有机器的过程，并计算最终获得的金币数量。然后，我们根据这个金币数量与 k 的比较来调整二分搜索的上下界。

下面是 C++ 实现的代码示例：

cpp
#include <iostream>  
#include <vector>  
using namespace std;  
  
long long getGold(const vector<int>& a, const vector<int>& b, long long silver) {  
    long long gold = 0;  
    for (int i = 0; i < a.size(); ++i) {  
        if (silver > a[i]) {  
            silver -= a[i];  
            gold += silver * b[i];  
        } else {  
            break;  // 银币不足，无法继续通过后续机器  
        }  
    }  
    return gold;  
}  
  
long long minSilver(const vector<int>& a, const vector<int>& b, int k) {  
    long long left = 0, right = 1e18, mid, result = 1e18;  
    while (left <= right) {  
        mid = left + (right - left) / 2;  
        if (getGold(a, b, mid) >= k) {  
            result = mid;  
            right = mid - 1;  // 尝试找到更小的银币数量  
        } else {  
            left = mid + 1;  
        }  
    }  
    return result;  
}  
  
int main() {  
    int T;  
    cin >> T;  
    while (T--) {  
        int n, 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];  
  
        cout << minSilver(a, b, k) << endl;  
    }  
    return 0;  
}

注意：

我们使用 long long 类型来处理银币和金币的数量，以避免整数溢出。
getGold 函数模拟了通过所有机器并计算金币数量的过程。
minSilver 函数使用二分搜索来找到最小的银币数量。
我们在二分搜索中逐步缩小搜索范围，直到找到最小的满足条件的银币数量。
考虑到 T 可能有多组数据，我们在 main 函数中通过循环来处理每一组数据。