算法

(贪心) $O(nlogn)$

1. 先对纪念品价格进行排序；
2. 开两个指针（左指针$l$和右指针$r$），从右开始与最左边的价格进行匹配，如果二者相加之和小于w 则cnt++，同时l++，r--，否则cnt++，r--。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3e4 + 10;

int n, w, cnt, a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> w >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int l = 1, r = n;
    while (l <= r) {
        if (a[r] + a[l] <= w) l++, r--;
        else r--;
        cnt++;
    }

    cout << cnt << '\n';

    return 0;
}