当前位置：首页 > article >正文

【华为OD机试真题】【2024年E卷】虚拟理财游戏-模拟贪心(C++/Java/Python)

article 2025/2/1 0:48:16

文章目录

- - 分值：100
  - 题目描述
  - 思路
  - 复杂度分析
  - AC 代码

分值：100

题目描述

在一款虚拟游戏中生活，你必须进行投资以增强在虚拟游戏中的资产以免被淘汰出局。现有一家Bank，它提供有若干理财产品 M 个，风险及投资回报不同，你有 N(元)进行投资，能接收的总风险值为X。你要在可接受范围内选择最优的投资方式获得最大回报备注：

在虚拟游戏中，每项投资风险值相加为总风险值；
在虚拟游戏中，最多只能投资2个理财产品；
在虚拟游戏中，最小单位为整数，不能拆分为小数；
投资额 * 回报率 = 投资回报。

输入描述:
第一行: M N X
第二行: 产品投资回报率只序列
第三行: 产品风险值序列
第四行: 最大投资额度序列
输出描述:
每个产品的投资额序列。

示例1
输入：
5 100 10
10 20 30 40 50
345610
20 30 20 40 30
输出：
0 30 0 40 0
解释：
投资第二项30个单位，第四项40个单位，总的投资风险为两项相加为4 + 6 = 10

Tips:

产品数，输入为整数，取值范围[1,20]
总投资额，输入为整数，取值范围[1,10000]
可接受的总风险，输入为整数，取值范围[1,200]
产品投资回报率只序列，输入为整数，取值范围[1,60]
产品风险值序列，输入为整数，取值范围[1,100]
最大投资额度序列，输入为整数，取值范围[1，10000]

思路

注意点1：最多只能投资2个理财产品。也就是可能没有可以选的理财产品或者只能选到一个理财产品，不能超过2件。
注意点2：设定了每个产品的最大投资额度以及可以用于投资的资金总额度。这就需要在每次抉择的时候判断每个选择的产品的额度是否满足条件以及每个产品加起来的额度之和是否超过总额度。
风险值跟投资额度无关，只要当前风险值不超过限定值，那么就尽可能投资，当选择了两个理财产品时，分别比较各自尽可能投资的收益再进行决策。一直选最大的收益即可，即贪心策略。

复杂度分析

时间复杂度： $O(N^2)$ ，其中N为产品数。
空间复杂度： $O (N)$ ，其中N为产品数。

AC 代码

C++ 版

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, x, maxEarning = 0, choiceIdxA = -1, choiceIdxB = -1, choiceInvestA = 0, choiceInvestB = 0;
    cin >> m >> n >> x;
    vector<int> earnings(m), risk(m), maxInvest(m), res(m, 0);
    for (int i = 0; i < m; i++)
    {
        cin >> earnings[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> risk[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> maxInvest[i];
    }
    for (int i = 0; i < m; i++)
    {
        // 只投资第 i 个产品的情况
        if (risk[i] > x)
        {
            continue;
        }
        int curEarningA = min(n, maxInvest[i]) * earnings[i];
        if (curEarningA > maxEarning)
        {
            choiceIdxA = i;
            choiceIdxB = -1;
            choiceInvestA = min(n, maxInvest[i]);
            choiceInvestB = 0;
            maxEarning = curEarningA;
        }
        // 只投资第 i 个产品跟第 j 个产品的情况
        for (int j = i + 1; j < m; j++)
        {
            if (risk[i] + risk[j] > x)
            {
                continue;
            }
            // 比较尽可能投资 A 和尽可能投资 B 的情况看看哪个收益更多（记得把剩余的钱投资到另外一个产品再比较）
            int curEarningB = min(n, maxInvest[j]) * earnings[j];
            int curMaxEarningA = curEarningA + min((n - min(n, maxInvest[i])), maxInvest[j]) * earnings[j],
                curMaxEarningB = curEarningB + min((n - min(n, maxInvest[j])), maxInvest[i]) * earnings[i];
            if (curMaxEarningA >= curMaxEarningB && curMaxEarningA > maxEarning)
            {
                // 这种情况是尽可能投资 A 的回报更大
                choiceIdxA = i;
                choiceIdxB = j;
                choiceInvestA = min(n, maxInvest[i]);
                choiceInvestB = min(n - choiceInvestA, maxInvest[j]);
                maxEarning = curMaxEarningA;
            }
            else if (curMaxEarningA <= curMaxEarningB && curMaxEarningB > maxEarning)
            {
                // 这种情况是尽可能投资 B 的回报更大
                choiceIdxA = i;
                choiceIdxB = j;
                choiceInvestB = min(n, maxInvest[j]);
                choiceInvestA = min(n - choiceInvestB, maxInvest[i]);
                maxEarning = curMaxEarningA;
            }
        }
    }
    if (choiceIdxA != -1)
    {
        res[choiceIdxA] = choiceInvestA;
    }
    if (choiceIdxB != -1)
    {
        res[choiceIdxB] = choiceInvestB;
    }
    for (auto v : res)
    {
        cout << v << " ";
    }
    return 0;
}

JAVA 版

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int x = scanner.nextInt();

        int maxEarning = 0, choiceIdxA = -1, choiceIdxB = -1, choiceInvestA = 0, choiceInvestB = 0;

        int[] earnings = new int[m];
        int[] risk = new int[m];
        int[] maxInvest = new int[m];
        int[] res = new int[m];

        for (int i = 0; i < m; i++) {
            earnings[i] = scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {
            risk[i] = scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {
            maxInvest[i] = scanner.nextInt();
        }

        for (int i = 0; i < m; i++) {
            if (risk[i] > x) {
                continue;
            }
            int curEarningA = Math.min(n, maxInvest[i]) * earnings[i];
            if (curEarningA > maxEarning) {
                choiceIdxA = i;
                choiceIdxB = -1;
                choiceInvestA = Math.min(n, maxInvest[i]);
                choiceInvestB = 0;
                maxEarning = curEarningA;
            }
            for (int j = i + 1; j < m; j++) {
                if (risk[i] + risk[j] > x) {
                    continue;
                }
                int curEarningB = Math.min(n, maxInvest[j]) * earnings[j];
                int curMaxEarningA = curEarningA + Math.min((n - Math.min(n, maxInvest[i])), maxInvest[j]) * earnings[j];
                int curMaxEarningB = curEarningB + Math.min((n - Math.min(n, maxInvest[j])), maxInvest[i]) * earnings[i];
                if (curMaxEarningA >= curMaxEarningB && curMaxEarningA > maxEarning) {
                    choiceIdxA = i;
                    choiceIdxB = j;
                    choiceInvestA = Math.min(n, maxInvest[i]);
                    choiceInvestB = Math.min(n - choiceInvestA, maxInvest[j]);
                    maxEarning = curMaxEarningA;
                } else if (curMaxEarningA <= curMaxEarningB && curMaxEarningB > maxEarning) {
                    choiceIdxA = i;
                    choiceIdxB = j;
                    choiceInvestB = Math.min(n, maxInvest[j]);
                    choiceInvestA = Math.min(n - choiceInvestB, maxInvest[i]);
                    maxEarning = curMaxEarningA;
                }
            }
        }

        if (choiceIdxA != -1) {
            res[choiceIdxA] = choiceInvestA;
        }
        if (choiceIdxB != -1) {
            res[choiceIdxB] = choiceInvestB;
        }

        for (int v : res) {
            System.out.print(v + " ");
        }
    }
}

Python 版

def main():
    m, n, x = map(int, input().split())

    maxEarning = 0
    choiceIdxA = -1
    choiceIdxB = -1
    choiceInvestA = 0
    choiceInvestB = 0

    earnings = list(map(int, input().split()))
    risk = list(map(int, input().split()))
    maxInvest = list(map(int, input().split()))

    res = [0] * m

    for i in range(m):
        if risk[i] > x:
            continue
        curEarningA = min(n, maxInvest[i]) * earnings[i]
        if curEarningA > maxEarning:
            choiceIdxA = i
            choiceIdxB = -1
            choiceInvestA = min(n, maxInvest[i])
            choiceInvestB = 0
            maxEarning = curEarningA
        for j in range(i + 1, m):
            if risk[i] + risk[j] > x:
                continue
            curEarningB = min(n, maxInvest[j]) * earnings[j]
            curMaxEarningA = curEarningA + min((n - min(n, maxInvest[i])), maxInvest[j]) * earnings[j]
            curMaxEarningB = curEarningB + min((n - min(n, maxInvest[j])), maxInvest[i]) * earnings[i]
            if curMaxEarningA >= curMaxEarningB and curMaxEarningA > maxEarning:
                choiceIdxA = i
                choiceIdxB = j
                choiceInvestA = min(n, maxInvest[i])
                choiceInvestB = min(n - choiceInvestA, maxInvest[j])
                maxEarning = curMaxEarningA
            elif curMaxEarningA <= curMaxEarningB and curMaxEarningB > maxEarning:
                choiceIdxA = i
                choiceIdxB = j
                choiceInvestB = min(n, maxInvest[j])
                choiceInvestA = min(choiceInvestB, maxInvest[i])
                maxEarning = curMaxEarningA

    if choiceIdxA != -1:
        res[choiceIdxA] = choiceInvestA
    if choiceIdxB != -1:
        res[choiceIdxB] = choiceInvestB

    for v in res:
        print(v, end=' ')

if __name__ == "__main__":
    main()