P4665 纪念品分组（基础）

解题思路

第一步，读懂题目。 要把纪念品分组，每组最多两件，价格和不能超过上限 w，要分组数最少。这是经典的贪心题。

第二步，想想生活里的例子。 两个人抬东西，最有力气的和最省力气的搭伙，尽量一次搬两件；如果两个人加起来太重，就让最重的那个自己先走。这样每组都能尽量装两件，组数自然最少。

第三步，定出贪心策略。 先把所有价格从小到大排序。用两个指针 left 和 right，left 指向当前最便宜的，right 指向当前最贵的。如果 price[left]+price[right]<=w，说明最贵和最便宜可以凑一组，left 往后移、right 往前移，组数加一；否则说明最贵的和谁凑都会超重，最贵的只能单独一组，right 往前移，组数加一。重复直到 left > right。

第四步，处理最后只剩一个。 当只剩一个纪念品时，它只能单独一组。所以循环用 while (left <= right) 控制，每一轮组数都加一，最后剩的那一个也会被算进组数里。

第五步，用样例验证。 样例中 w=100，价格 20、20、30、50、60、70、80、90、90。最贵的 90 和最便宜的 20 加起来 110 超重，所以 90 先单独走；接着另一个 90 和 20 一组正好 100；然后是 80+20、70+30、60+50 各一组；最后剩下 50 单独一组，一共 6 组。

第六步，理解贪心的正确性。 每次让最贵的尽量带走一个最便宜的，能配就配，能省一组是一组。这样得到的组数是最少的，这就是贪心算法"每一步选当前最优"的思想。

参考代码

// P4665 纪念品分组：价格升序排序，最贵与最便宜配对，放不下就贵的单独一组
#include <iostream>
#include <algorithm>
int main() {
    int w, n;
    std::cin >> w >> n;
    int price[100005];
    for (int i = 0; i < n; i++) std::cin >> price[i];
    std::sort(price, price + n);   // 价格从小到大
    int left = 0, right = n - 1, groupCnt = 0;
    while (left <= right) {
        if (left < right && price[left] + price[right] <= w) left++;   // 最便宜的和最贵的一起放
        right--;                                                       // 最贵的(或剩下的最后一个)已处理
        groupCnt++;
    }
    std::cout << groupCnt << "\n";
    return 0;
}

复杂度分析

排序用 O(n log n)，两指针扫描一遍是 O(n)，总时间复杂度 O(n log n)。n 最多 30000 左右，很快。空间上只需要一个数组存价格，O(n)。这道题的关键是想通"最贵的先处理、能配就配最便宜的"这个贪心策略，再用两个指针高效实现。