Tính tiền tối đa sau khi mua bán cổ phiếu bằng C++

Mô tả bài toán

Có n cơ hội mua (giá A[i]), m cơ hội bán (giá B[i]). Vốn ban đầu r, không cổ phiếu ban đầu. Mua bao nhiêu tùy thích, bán không quá số có. Tìm tiền tối đa sau khi mua bán.

Ví dụ

A=[4,2,5], B=[4,4,5,4], r=11 → Mua giá rẻ nhất 2, bán giá cao nhất 5. Mua 5 cổ phiếu (10 tiền), bán 5*5=25, dư 1 → tổng 26.

Thuật toán

Tìm giá mua nhỏ nhất (an), giá bán lớn nhất (bn). Nếu bn > an thì mua nhiều nhất có thể: shares = r / an, tiền = bn*shares + (r % an). Ngược lại giữ nguyên r.

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, vector<int> B, int r) {
    int an = 1100, bn = 0;
    for (int x : A) an = min(an, x);
    for (int x : B) bn = max(bn, x);
    if (bn > an) {
        int shares = r / an;
        r = bn * shares + (r - shares * an);
    }
    return r;
}

int main() {
    vector<int> A = {4,2,5};
    vector<int> B = {4,4,5,4};
    int r = 11;
    cout << solve(A, B, r) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {4,2,5}, {4,4,5,4}, 11

Output: 26