E卷-最大利润-贪心的商人(100分)

最大利润-贪心的商人

问题描述

商人经营一家店铺，有 种商品，由于仓库限制每件商品的最大持有数量是 ，每种商品的价格是 。

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

输入格式

第一行输入一个整数 ，表示商品的数量。

第二行输入一个整数 ，表示售货天数。

第三行输入 个整数，表示仓库限制每件商品的最大持有数量 。

接下来 行，每行包含 个整数，表示每种商品在每天的价格 。

输出格式

输出一个整数，表示商人在这段时间内的最大利润。

样例输入

3
3
4 5 6
1 2 3
4 3 2
1 5 2

样例输出

32

样例解释

对于第一种商品，可以在第一天以 1 的价格买入 4 个，在第三天以 3 的价格卖出，获利 (3-1)*4 = 8。 对于第二种商品，可以在第二天以 3 的价格买入 5 个，在第一天以 4 的价格卖出，获利 (4-3)*5 = 5。 对于第三种商品，可以在第一天以 1 的价格买入 6 个，在第二天以 5 的价格卖出，获利 (5-1)*6 = 24。 总利润为 8 + 5 + 24 = 37。

样例输入

1
1
1
1

样例输出

0

样例解释

只有一种商品，只有一天，无法获得利润。

数据范围

题解

这道题的核心思路是利用贪心算法来解决。

虽然看起来像是一个复杂的动态规划问题，但实际上有一个更简单的解法。

关键在于理解：只要价格在上涨，我们就应该持有商品；只要价格在下跌，我们就应该卖出商品。

这样，我们可以捕捉到每一个价格上涨的机会，从而最大化利润。

遍历每种商品的价格序列。对于每种商品，我们比较相邻两天的价格：

1. 如果明天的价格高于今天，我们就在今天买入（如果没有持有），明天卖出。
2. 如果明天的价格低于或等于今天，我们就不进行任何操作。

参考代码

• Python

# 读取输入
number = int(input())  # 商品数量
days = int(input())    # 售货天数
item = list(map(int, input().split()))  # 每种商品的最大持有数量
prices = [list(map(int, input().split())) for _ in range(number)]  # 每种商品每天的价格

# 初始化总利润
total_profit = 0

# 遍历每种商品
for i in range(number):
    # 遍历该商品的每一天（除了最后一天）
    for j in range(days - 1):
        # 如果明天的价格高于今天，就在今天买入，明天卖出
        if prices[i][j] < prices[i][j + 1]:
            # 计算利润：（明天价格 - 今天价格）* 最大持有数量
            profit = (prices[i][j + 1] - prices[i][j]) * item[i]
            # 累加到总利润
            total_profit += profit

# 输出最大利润
print(total_profit)

• C

#include <stdio.h>
#include <stdlib.h>

int main() {
    int number, days;
    scanf("%d", &number);  // 读取商品数量
    scanf("%d", &days);    // 读取售货天数

    int* item = (int*)malloc(number * sizeof(int));  // 动态分配内存存储最大持有数量
    for (int i = 0; i < number; i++) {
        scanf("%d", &item[i]);  // 读取每种商品的最大持有数量
    }

    int** prices = (int**)malloc(number * sizeof(int*));  // 动态分配二维数组存储价格
    for (int i = 0; i < number; i++) {
        prices[i] = (int*)malloc(days * sizeof(int));
        for (int j = 0; j < days; j++) {
            scanf("%d", &prices[i][j]);  // 读取每种商品每天的价格
        }
    }

    long long total_profit = 0;  // 使用长整型避免溢出

    // 遍历每种商品
    for (int i = 0; i < number; i++) {
        // 遍历该商品的每一天（除了最后一天）
        for (int j = 0; j < days - 1; j++) {
            // 如果明天的价格高于今天，就在今天买入，明天卖出
            if (prices[i][j] < prices[i][j + 1]) {
                // 计算利润并累加到总利润
                total_profit += (long long)(prices[i][j + 1] - prices[i][j]) * item[i];
            }
        }
    }

    printf("%lld\n", total_profit);  // 输出最大利润

    // 释放动态分配的内存
    for (int i = 0; i < number; i++) {
        free(prices[i]);
    }
    free(prices);
    free(item);

    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let number, days, item, prices = [];
let lineCount = 0;

rl.on('line', (line) => {
    if (lineCount === 0) {
        number = parseInt(line);  // 读取商品数量
    } else if (lineCount === 1) {
        days = parseInt(line);    // 读取售货天数
    } else if (lineCount === 2) {
        item = line.split(' ').map(Number);  // 读取每种商品的最大持有数量
    } else {
        prices.push(line.split(' ').map(Number));  // 读取每种商品每天的价格
    }

    lineCount++;

    if (lineCount === number + 3) {
        rl.close();
    }
});

rl.on('close', () => {
    let totalProfit = 0;

    // 遍历每种商品
    for (let i = 0; i < number; i++) {
        // 遍历该商品的每一天（除了最后一天）
        for (let j = 0; j < days - 1; j++) {
            // 如果明天的价格高于今天，就在今天买入，明天卖出
            if (prices[i][j] < prices[i][j + 1]) {
                // 计算利润并累加到总利润
                totalProfit += (prices[i][j + 1] - prices[i][j]) * item[i];
            }
        }
    }

    console.log(totalProfit);  // 输出最大利润
});

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int number = scanner.nextInt();  // 读取商品数量
        int days = scanner.nextInt();    // 读取售货天数
        
        int[] item = new int[number];    // 存储每种商品的最大持有数量
        for (int i = 0; i < number; i++) {
            item[i] = scanner.nextInt();
        }
        
        int[][] prices = new int[number][days];  // 存储每种商品每天的价格
        for (int i = 0; i < number; i++) {
            for (int j = 0; j < days; j++) {
                prices[i][j] = scanner.nextInt();
            }
        }
        
        long totalProfit = 0;  // 使用long类型避免溢出
        
        // 遍历每种商品
        for (int i = 0; i < number; i++) {
            // 遍历该商品的每一天（除了最后一天）
            for (int j = 0; j < days - 1; j++) {
                // 如果明天的价格高于今天，就在今天买入，明天卖出
                if (prices[i][j] < prices[i][j + 1]) {
                    // 计算利润并累加到总利润
                    totalProfit += (long)(prices[i][j + 1] - prices[i][j]) * item[i];
                }
            }
        }
        
        System.out.println(totalProfit);  // 输出最大利润
        
        scanner.close();
    }
}

• Cpp

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

int main() {
    int number, days;
    cin >> number >> days;  // 读取商品数量和售货天数

    vector<int> item(number);  // 存储每种商品的最大持有数量
    for (int i = 0; i < number; i++) {
        cin >> item[i];
    }

    vector<vector<int>> prices(number, vector<int>(days));  // 存储每种商品每天的价格
    for (int i = 0; i < number; i++) {
        for (int j = 0; j < days; j++) {
            cin >> prices[i][j];
        }
    }

    long long totalProfit = 0;  // 使用long long避免溢出

    // 遍历每种商品
    for (int i = 0; i < number; i++) {
        // 遍历该商品的每一天（除了最后一天）
        for (int j = 0; j < days - 1; j++) {
            // 如果明天的价格高于今天，就在今天买入，明天卖出
            if (prices[i][j] < prices[i][j + 1]) {
                // 计算利润并累加到总利润
                totalProfit += (long long)(prices[i][j + 1] - prices[i][j]) * item[i];
            }
        }
    }

    cout << totalProfit << endl;  // 输出最大利润

    return 0;
}