练75.2采购奖品

解题思路

按单价升序买奖品，每种能买min(库存,余额/单价)件，扣除费用继续。低价优先能使相同预算购买件数最多。

正确性说明

若已买贵奖品而便宜奖品有余货，替换成便宜件不会减少件数且释放预算。因此存在低价优先的最优方案，逐种尽量购买即可达到最优件数。

易错点

库存有限，不是每种无限购买；输出件数不是花费。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long money;
    int n;
    cin >> money >> n;
    vector<pair<long long, int>> a(n);
    for (auto &p : a)
        cin >> p.first >> p.second;
    sort(a.begin(), a.end());
    long long count = 0;
    for (auto p : a) {
        long long k = min<long long>(p.second, money / p.first);
        count += k;
        money -= k * p.first;
    }
    cout << count << "\n";
    return 0;
}