P4800 分配礼物（基础）

解题思路

1. 读懂题目：有 n 件礼物，每组最多装 2 件，而且每组的价值总和不能超过 y。为了让组数尽量少，就要让"两个人领一组"的组合尽量多。题目问"有多少同学领到两个礼物"，其实就是问能配成几组两人的礼物组合。

2. 打个比方：这就像坐观光缆车，每辆缆车最多坐 2 人，而且总重量不能超过 y。想让缆车的数量最少，最轻的小朋友应该和最重的、能和他一起坐的小朋友同车，这样才不会浪费位置。

3. 第一步：先把所有礼物的价值从小到大排序，价值小的排前面。这样方便用两个指针从两头往中间找。

4. 第二步：用两个指针，左指针指当前最轻的礼物，右指针指当前最重的礼物。如果"最轻 + 最重 ≤ y"，说明这两件礼物正好能凑成一组，两人都能领到两件礼物，计数加 1，然后左指针右移、右指针左移。

5. 第三步：如果"最轻 + 最重 > y"，说明最重的那件礼物太重，谁也配不上它，它只能被一位同学单独领走，右指针左移。

6. 第四步：重复上面的过程，直到左右指针相遇或者左指针跑到右指针右边为止。最后输出配对的组数。

7. 边界情况：如果所有礼物都很轻，大家都能两两配对，配对数量最多；如果有礼物特别重，它只能单独一组；当 n 是奇数时，最后一定会剩下一件礼物单独一组，这很正常。

参考代码

// P4800 分配礼物：双指针贪心，把最轻和最重的礼物尽量配对，统计凑成两件一组的对数
#include <iostream>
#include <algorithm>
using namespace std;

long long giftValue[200005];   // 每件礼物的价值

int main() {
    int n;
    long long limit;   // 每组礼物价值不能超过 limit
    cin >> n >> limit;
    for (int i = 0; i < n; i++) cin >> giftValue[i];
    // 礼物价值从小到大排序
    sort(giftValue, giftValue + n);
    int left = 0, right = n - 1;   // 左指针指向最轻的礼物，右指针指向最重的礼物
    int pairCount = 0;             // 能拿到两件礼物的同学人数
    while (left < right) {
        if (giftValue[left] + giftValue[right] <= limit) {
            pairCount++;            // 最轻和最重正好能凑一组，两人都领到两件礼物
            left++;
            right--;
        } else {
            right--;                // 最重那件太重，只能一个人单独领一组
        }
    }
    cout << pairCount << endl;
    return 0;
}

复杂度分析

排序用 sort，需要 O(n log n) 的时间；排序后用两个指针从两端往中间扫描，只需要 O(n) 的时间，所以总时间复杂度是 O(n log n)。数组只需要存 n 件礼物的价值，空间复杂度是 O(n)。