P4387 买大米（入门）

解题思路

小童家每年要买 n 次大米，每次有价格 p 和斤数 w，这次的花费就是 p × w。题目要找出 n 次里花费最少的一次。

最直接的办法是"打擂台"：先在擂台旁边放一个特别大的数当作"当前最强者"，然后每算出一笔花费，就跟擂台上的数比一比，如果更小就把它换到擂台上。所有数据看完后，擂台上剩下的就是最小值。

拿样例验证：第一次 2 × 20 = 40，第二次 3 × 10 = 30，第三次 3 × 15 = 45。40 先上台，30 更小换上去，45 比 30 大不动，所以最小花费是 30 元，和样例一致。

边界情况：擂台初始值 mn 一定要设得足够大，比如 2000000000，否则第一个数来了没法比。题目保证 n 是正整数，所以至少有一次购物，最后一定有答案；还保证每次花费不超过 200 元，所以用 int 就够装，p × w 也不会超范围。

参考代码

// 程序用途：求出n次买大米中花费最少的一次的钱数
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int mn = 2000000000;              // mn记录最小花费，先设成一个很大的数
    for (int i = 0; i < n; i++) {
        int p, w;
        cin >> p >> w;                // 读入这次的价格和斤数
        int c = p * w;                // 这次的花费 = 价格 × 斤数
        if (c < mn) mn = c;           // 打擂台：更小就更新记录
    }
    cout << mn << endl;
    return 0;
}

复杂度分析

读入并计算 n 次，循环 n 次，时间复杂度是 O(n)；空间上只用一个记录最小值的变量，额外空间复杂度是 O(1)。