C++ 编程题：小明逛商场

小明是个不太有计划的孩子。这不，刚到手的零花钱，就全部拿着逛商场去了。小明的原则很简单，只要见到想买的物品而且能买得起，就一定会买下来之后才会继续往前走。一天下来，小明到底买了多少物品呢？

输入格式 输入共 3 行：

第一行为一个整数 N，表示商场中共有 N 种小明想买的物品（1 ≤ N ≤ 100）；
第二行共有 N 个整数，分别表示小明先后见到想买的物品的价格；
第三行为一个整数 X，表示开始时小明共有 X 元零花钱。

输出格式 输出 1 行，包含一个整数，表示小明买到的物品数。

输入输出样例

样例 1

输入样例:

6
7 5 9 10 7 4
30

输出样例:

思路按照题意，小明拿到零花钱后，只要见到想买的物品且能买得起，就一定会买下来。所以可以按照顺序遍历物品的价格，判断是否能买得起，并累加购买的物品数量。

代码

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

int main() {
    int N;
    cin >> N;
    vector<int> prices(N);
    for (int i = 0; i < N; i++) {
        cin >> prices[i];
    }
    int X;
    cin >> X;
    
    int count = 0; // 购买的物品数量
    int sum = 0; // 已花费的零花钱总和
    for (int i = 0; i < N; i++) {
        if (sum + prices[i] <= X) { // 如果能买得起，则购买该物品
            count++;
            sum += prices[i];
        }
    }
    
    cout << count << endl;
    
    return 0;
}

复杂度分析

时间复杂度：O(N)，其中 N 为物品的数量。遍历一遍物品的价格，判断是否能买得起。
空间复杂度：O(N)，使用一个数组存储物品的价格。