P4802 上船问题（基础）

解题思路

1. 读懂题目：有 n 个人要坐船过河，每艘船最多坐 2 个人，最大载重是 m。问最少需要多少艘船才能把所有人运过去。

2. 打个比方：这就像玩"找伙伴坐船"的游戏。为了让船最少，最轻的人应该和最重的、能和他同船的人坐在一起；如果最重的人连最轻的人都带不动，那他就只能自己坐一艘船。

3. 第一步：先把所有人的体重从小到大排序，体重轻的排前面。

4. 第二步：用两个指针，左指针指最轻的人，右指针指最重的人。

5. 第三步：如果"最轻 + 最重 ≤ m"，说明这两个人能坐同一艘船，船数加 1，然后左指针右移、右指针左移。

6. 第四步：如果"最轻 + 最重 > m"，说明最重的人谁也带不动他，他必须单独坐一艘船，船数加 1，只把右指针左移。

7. 第五步：循环直到两个指针相遇。如果最后恰好只剩下一个人，让他单独坐一艘船。

8. 为什么贪心正确：最重的人如果和最轻的人都无法同船，那他和任何人都无法同船，只能独占一艘；如果他能和最轻的人同船，那这样配是损失最小的组合。

9. 边界情况：如果所有人两两都能配对，船数最少是 n/2 向上取整；如果每艘船都只能坐一个人，船数就是 n。

参考代码

// P4802 上船问题：双指针贪心，最轻的人尽量和最重的能同船的人坐一起，求最少船只数
#include <iostream>
#include <algorithm>
using namespace std;

long long weight[200005];   // 每个人的体重

int main() {
    int n;
    long long maxLoad;   // 每艘船的最大载重
    cin >> n >> maxLoad;
    for (int i = 0; i < n; i++) cin >> weight[i];
    // 体重从小到大排序
    sort(weight, weight + n);
    int left = 0, right = n - 1;   // 左指针最轻、右指针最重
    int boatCount = 0;             // 需要的船数
    while (left <= right) {
        if (left == right) {
            // 只剩一个人，自己坐一艘船
            boatCount++;
            break;
        }
        if (weight[left] + weight[right] <= maxLoad) {
            // 最轻的和最重的能坐同一艘船
            boatCount++;
            left++;
            right--;
        } else {
            // 最重的太重，只能单独坐一艘船
            boatCount++;
            right--;
        }
    }
    cout << boatCount << endl;
    return 0;
}

复杂度分析

排序需要 O(n log n) 的时间；排序后左右两个指针各走一遍，只需要 O(n) 的时间。所以总时间复杂度是 O(n log n)，空间复杂度是 O(n)。