题解 | #买面包#

题目链接

买面包

题目描述

小明在超市购物，需要计算购物篮中所有面包的总价格。

已知超市中面包的总类型数 $n$ ，以及每种面包的单价。同时，也知道小明购买的每种面包的编号和对应的数量。

输入格式：

第一行一个整数 $n$ ，表示面包的总类型数。
第二行 $n$ 个整数，表示第 1 种到第 $n$ 种面包的单价。
第三行一个整数 $m$ ，表示购买记录的数量。
接下来 $m$ 行，每行有两个整数 $x, y$ ，表示购买了 $y$ 个第 $x$ 种面包。

输出格式：

输出一个整数，表示购买所有面包的总价格。

解题思路

这是一个直接的模拟计算问题。算法的核心是根据输入的购买记录，查找对应面包的单价，然后计算每条记录的费用，最后将所有费用累加起来。

算法流程：

存储价格：
- 读入面包的总类型数 $n$ 。
- 创建一个数组或列表（例如 prices），大小为 $n$ 。
- 读入 $n$ 个面包的单价，并存入 prices 数组中。由于题目中的面包编号 $x$ 是从 1 开始的 (1-indexed)，而数组索引通常是从 0 开始的 (0-indexed)，所以在访问价格时，需要用 prices[x-1] 来获取第 $x$ 种面包的价格。
计算总价：
- 初始化一个变量 total_price 为 0，用于累计总价格。为了防止整数溢出（虽然本题数据范围较小，但这是一个好习惯），可以使用 long long (C++) 或 long (Java) 类型。
- 读入购买记录的数量 $m$ 。
- 使用一个循环，重复 $m$ 次，处理每一条购买记录： a. 在循环的每一次迭代中，读入面包编号 $x$ 和购买数量 $y$ 。 b. 通过 prices[x-1] 获取第 $x$ 种面包的单价。 c. 计算当前记录的花费：cost = prices[x-1] * y。 d. 将这个花费累加到 total_price 中：total_price += cost。
输出结果：
- 循环结束后，total_price 中存储的就是所有面包的总价格。将其输出。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        cin >> prices[i];
    }

    int m;
    cin >> m;

    ll total_price = 0;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        // 面包编号 x 是 1-indexed, 数组索引是 0-indexed
        total_price += (ll)prices[x - 1] * y;
    }

    cout << total_price << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = sc.nextInt();
        }

        int m = sc.nextInt();
        long totalPrice = 0;
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            // 面包编号 x 是 1-indexed, 数组索引是 0-indexed
            totalPrice += (long) prices[x - 1] * y;
        }

        System.out.println(totalPrice);
    }
}

import sys

def main():
    try:
        # 读入面包种类数 n
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)

        # 读入 n 种面包的价格
        prices = list(map(int, sys.stdin.readline().strip().split()))

        # 读入购买记录数 m
        m_str = sys.stdin.readline()
        if not m_str: return
        m = int(m_str)

        total_price = 0
        for _ in range(m):
            line = sys.stdin.readline()
            if not line: break
            x, y = map(int, line.strip().split())
            # 面包编号 x 是 1-indexed, 列表索引是 0-indexed
            total_price += prices[x - 1] * y
        
        print(total_price)

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：模拟
时间复杂度： $\mathcal{O}(N + M)$ ，其中 $N$ 是面包的种类数， $M$ 是购买记录的数量。我们需要 $\mathcal{O}(N)$ 的时间来读取所有面包的价格，以及 $\mathcal{O}(M)$ 的时间来处理所有的购买记录。
空间复杂度： $\mathcal{O}(N)$ 。需要一个大小为 $N$ 的数组来存储所有种类面包的单价。