P4798 士兵突击（入门）

解题思路

1. 读懂题目：n 名士兵要坐船偷袭，船只能运一次，船的载重量固定。每名士兵有自己的体重，问一次最多能运送多少名士兵。只要总体重不超过载重量，就可以一起上船。

2. 打个比方：就像坐电梯，电梯有载重限制，想一次多送几个人上楼，当然先让体重轻的人上，这样能挤进更多人。

3. 贪心结论：把士兵的体重从轻到重排序，然后从最轻的开始，一个一个试着装，装得下就装，一旦装不下，后面更重的更装不下，就停止。

4. 为什么从小到大装是最优的：我们想装的人数最多。如果装了某个较重的士兵而挤掉了两个轻的士兵，人数反而少了。所以应该优先选体重最轻的一批人。排序后从最轻的装起，保证在载重量限制下装的人数最多。

5. 看例子：样例体重 7,2,6,4,5，排序后是 2,4,5,6,7，船载重量 11。装 2，累计 2；装 4，累计 6；装 5，累计 11，正好装满，共 3 名士兵。再想装 6，11+6=17 就超载了。

6. 边界情况：如果最轻的士兵体重都比载重量大，那一名也装不了，输出 0；如果所有士兵体重加起来都不超过载重量，那就能全部装下。

7. 小细节：体重用整数，排序用简单的冒泡排序就够了，因为士兵数量小于 2000，体重小于 300。

参考代码

// P4798 士兵突击：船载重有限，先装最轻的士兵，数量才能最多
#include <iostream>
using namespace std;
int weight[2005];  // 每名士兵的体重

int main() {
    int n, shipLoad;
    cin >> n >> shipLoad;
    for (int i = 0; i < n; i++) cin >> weight[i];
    // 体重升序排序（冒泡排序，轻的排前面）
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (weight[j] > weight[j + 1]) { int temp = weight[j]; weight[j] = weight[j + 1]; weight[j + 1] = temp; }
    int count = 0;  // 装进船的士兵数量
    int sum = 0;    // 已装士兵的总重量
    for (int i = 0; i < n; i++) {
        if (sum + weight[i] <= shipLoad) {
            // 装得下就装，尽量多装
            sum += weight[i];
            count++;
        } else break;  // 再重的更装不下了
    }
    cout << count << endl;
    return 0;
}

复杂度分析

冒泡排序的时间是 O(n²)，n<2000，大约四百万次比较，可以接受；扫描一遍判断装载是 O(n)。空间上只用了一个长度为 2005 的数组，是 O(n)。整个算法简单直接，很容易理解，是贪心思想最基础的运用。