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

【OD】【E卷】【真题】【100分】最大利润贪心的商人（PythonJavaJavaScriptC++C）

news 2024/10/22 11:23:45

题目描述

商人经营一家店铺，有number种商品，由于仓库限制每件商品的最大持有数量是item[index]，每种商品的价格是item-price[item_index][day]

通过对商品的买进和卖出获取利润，请给出商人在days天内能获取的最大的利润
注：同一件商品可以反复买进和卖出

输入描述

第一行输入商品的数量number，比如3
第二行输入商品售货天数 days，比如3
第三行输入仓库限制每件商品的最大持有数量是item[index]，比如4 5 6

后面继续输入number行days列，含义如下：
第一件商品每天的价格，比如1 2 3
第二件商品每天的价格，比如4 3 2
第三件商品每天的价格，比如1 5 3

输出描述

输出商人在这段时间内的最大利润。

示例1

输入

输出

示例2

输入

输出

解题思路

我们只要找到商品价格走势的上升区段，然后低价买入，高价卖出即可求得最大利润。

和lettcode上的这题差不多！

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

使用贪心算法来计算每天售卖商品能够获得的最大利润。

Java

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;class Main {public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);int itemNumber = in.nextInt(); // 商品数量int days = in.nextInt(); // 售货天数int[] maxItems = new int[itemNumber]; // 每件商品最大持有数量for (int i = 0; i < itemNumber; i++) {maxItems[i] = in.nextInt();}int[][] prices = new int[itemNumber][days]; // 商品价格列表for (int i = 0; i < itemNumber; i++) {for (int j = 0; j < days; j++) {prices[i][j] = in.nextInt();}}// 贪心算法int maxProfit = 0;for (int i = 0; i < itemNumber; i++) { // 遍历每件商品for (int j = 1; j < days; j++) { // 遍历商品价格列表，求出每天的利润int profit = Math.max(0, prices[i][j] - prices[i][j - 1]);// 当前价格减去前一天价格，如果为负数则代表亏本，不计入利润maxProfit += profit * maxItems[i]; // 求出当前商品能够获取的最大利润}}System.out.println(maxProfit); // 输出最大利润}
}

Python

# 处理输入
itemNumber = int(input())  # 商品数量
days = int(input())  # 售货天数maxItems = list(map(int, input().split()))  # 每件商品最大持有数量prices = [list(map(int, input().split())) for _ in range(itemNumber)]  # 商品价格列表# 贪心算法
maxProfit = 0
for i in range(itemNumber):  # 遍历每件商品for j in range(1, days):  # 遍历商品价格列表，求出每天的利润profit = max(0, prices[i][j] - prices[i][j - 1])# 当前价格减去前一天价格，如果为负数则代表亏本，不计入利润maxProfit += profit * maxItems[i]  # 求出当前商品能够获取的最大利润print(maxProfit)  # 输出最大利润

JavaScript

const readline = require('readline').createInterface({input: process.stdin,output: process.stdout,
});// 处理输入
let input = [];
readline.on('line', (line) => {input.push(line);
});readline.on('close', () => {const itemNumber = parseInt(input[0])const days = parseInt(input[1]); // 商品数量和售货天数const maxItems = input[2].split(' ').map(Number); // 每件商品最大持有数量const prices = input.slice(3).map((line) => line.split(' ').map(Number)); // 商品价格列表let maxProfit = 0;for (let i = 0; i < itemNumber; i++) { // 遍历每件商品for (let j = 1; j < days; j++) { // 遍历商品价格列表，求出每天的利润const profit = Math.max(0, prices[i][j] - prices[i][j - 1]);// 当前价格减去前一天价格，如果为负数则代表亏本，不计入利润maxProfit += profit * maxItems[i]; // 求出当前商品能够获取的最大利润}}console.log(maxProfit); // 输出最大利润
});

C++

#include <iostream>
#include <vector>
using namespace std;int main() {// 处理输入int itemNumber, days;cin >> itemNumber >> days;vector<int> maxItems(itemNumber); // 每件商品最大持有数量for (int i = 0; i < itemNumber; i++) {cin >> maxItems[i];}vector<vector<int>> prices(itemNumber, vector<int>(days)); // 商品价格列表for (int i = 0; i < itemNumber; i++) {for (int j = 0; j < days; j++) {cin >> prices[i][j];}}// 贪心算法int maxProfit = 0;for (int i = 0; i < itemNumber; i++) { // 遍历每件商品for (int j = 1; j < days; j++) { // 遍历商品价格列表，求出每天的利润int profit = max(0, prices[i][j] - prices[i][j - 1]);// 当前价格减去前一天价格，如果为负数则代表亏本，不计入利润maxProfit += profit * maxItems[i]; // 求出当前商品能够获取的最大利润}}cout << maxProfit << endl; // 输出最大利润return 0;
}

C语言

#include <stdio.h>int max(int a, int b) {return (a > b) ? a : b; // 返回两个整数中的较大值
}int main() {// 处理输入int itemNumber; // 商品数量int days; // 售货天数// 从标准输入读取商品数量和售货天数scanf("%d %d", &itemNumber, &days);int maxItems[itemNumber]; // 每件商品的最大持有数量for (int i = 0; i < itemNumber; i++) {scanf("%d", &maxItems[i]); // 读取每件商品的最大持有数量}int prices[itemNumber][days]; // 商品价格列表，二维数组存储for (int i = 0; i < itemNumber; i++) {for (int j = 0; j < days; j++) {scanf("%d", &prices[i][j]); // 读取每件商品在每一天的价格}}// 贪心算法计算最大利润int maxProfit = 0; // 初始化最大利润为0for (int i = 0; i < itemNumber; i++) { // 遍历每件商品for (int j = 1; j < days; j++) { // 遍历每一天的价格// 当前价格减去前一天的价格，计算利润int profit = max(0, prices[i][j] - prices[i][j - 1]);// 如果利润为正，则将其乘以该商品的最大持有量，加到总利润中maxProfit += profit * maxItems[i];}}// 输出最大利润printf("%d\n", maxProfit);return 0;
}