P4345 药房管理（【基础】）

解题思路

这道题要模拟"发药"的过程。药房一开始有 $m$ 盒库存，病人按顺序一个一个来取药，每个人想要的数量是 $x$：

• 如果库存够（$x \le m$），就把药给他，库存减少 $x$；
• 如果库存不够（$x > m$），拒绝这个病人，没取上药的人数加 1。

把每个病人想取的数量读进来，一边读一边判断，最后输出没取上药的人数。这里要特别小心：被拒绝的病人并不消耗库存，所以库存只在"够"的时候才减。

拿样例来说：库存 30，六个病人分别要 10、5、20、6、7、8。

• 要 10：够，库存变 20；
• 要 5：够，库存变 15；
• 要 20：库存只剩 15，不够，拒绝，计数 1；
• 要 6：够，库存变 9；
• 要 7：够，库存变 2；
• 要 8：库存只剩 2，不够，拒绝，计数 2。 最后输出 2，和样例一致。

边界情况：如果某个病人要的数量正好等于库存，比如库存 10 时病人要 10，那是够的，取走后库存变 0，后面再来人就都会被拒绝。题目保证人数 $n>0$。

参考代码

// 模拟药房取药过程，统计没取上药的人数
#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;      // m为库存总量，n为取药人数
    int cnt = 0;        // 没取上药的人数计数器
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;       // 当前病人想要的数量
        if (x <= m) m -= x;   // 库存够，扣掉
        else cnt++;           // 库存不够，拒绝并计数
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

每个病人处理一次，一共 $n$ 个人，所以时间复杂度是 $O(n)$（$n$ 最大 100，非常快）。只用几个整数变量，没有用数组，额外空间复杂度是 $O(1)$。