P4412 买大米（入门）

解题思路

题目给出n次购物，每次给价格p和斤数w，一次的花费就是 p×w，要找出哪一次花钱最少。我们可以用"打擂台"的方法：先假设最少的钱是ans，一开始把它设成一个非常大的数（比如20亿），因为20亿肯定比任何一次真实花费都大，这样第一次比较时必然能更新成第一笔花费。然后用for循环把n次购物都读进来，每算出一笔花费s，就跟擂台上的ans比一比：如果s更小，就把s推上擂台（ans=s）。循环结束后，擂台上的ans就是所有花费里最小的那个。边界情况：如果n=1，只有一笔花费，循环只执行一次，ans会从20亿直接更新成这一笔的钱，结果正确。题目保证每笔花费不超过200元，所以 p×w 的乘积不会溢出int。

参考代码

// 程序用途：读入n次买大米的价格和斤数，求出其中花费最少的一次
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 2000000000;           // 答案先设成很大，方便打擂台
    for (int i = 1; i <= n; i++) {
        int p, w;
        cin >> p >> w;
        int s = p * w;              // 这次花费 = 价格 × 斤数
        if (s < ans) ans = s;       // 比当前最小还小就更新答案
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

用for循环把n笔购物各处理一遍，每笔只做一次乘法和一次比较，所以时间复杂度 O(n)；整个过程只用了几个变量存当前值，没有用数组，额外空间复杂度 O(1)。