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

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<long long> 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 l = 0, r = 1e18;
        while (l < r) {
            long long mid = l + (r - l) / 2;
            long long coins = mid;
            for (int i = 0; i < n; ++i) {
                if (coins <= a[i]) continue;
                coins -= a[i];
                coins += min(coins / b[i], (long long)1e9);
            }
            if (coins >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        cout << l << endl;
    }
    return 0;
}