文字教学

这道题用贪心算法+双指针解决，核心思路是让“最小的和最大的尽量凑一组”，最大化利用每组价格上限以减少分组数：

1. 先将所有纪念品价格从小到大排序（用快速排序保证效率）。
2. 用左指针 l 指向当前最小价格，右指针 r 指向当前最大价格：
   • 若两者价格和不超过上限，就凑成一组，同时移动两个指针；
   • 若超过上限，最大的只能单独一组，只移动右指针。
3. 每处理一个（或两个）纪念品，分组数+1，直到所有纪念品处理完。

代码

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

int p[30005], w, n, ans, l, r;

void qs(int l, int r) {
    if (l >= r) return;
    int i = l, j = r, mid = p[(l + r) / 2];
    while (i <= j) {
        while (p[i] < mid) i++;
        while (p[j] > mid) j--;
        if (i <= j) {
            swap(p[i], p[j]);
            i++; j--;
        }
    }
    qs(l, j);
    qs(i, r);
}

int main() {
    cin >> w >> n;
    for (int i = 0; i < n; ++i) cin >> p[i];
    qs(0, n - 1);
    l = 0; r = n - 1;
    while (l <= r) {
        if (p[l] + p[r] <= w) l++;
        r--; ans++;
    }
    cout << ans << endl;
    return 0;
}