python/TangDou/XiTi/1266.cpp

#include <bits/stdc++.h>

using namespace std;

int t[1001] = {0};

int main() {
    //输入+输出重定向
    freopen("../1266.txt", "r", stdin);

    int w, n;
    cin >> w;  //表示每条独木舟最大的载重量。
    cin >> n;  //表示参加旅行的人数。
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    //排序,从大到小
    sort(t + 1, t + n + 1, greater<int>());
    //需要的独木舟数
    int count = 0;

    //遍历数组，如果已经上船了，就标识为-1
    for (int i = 1; i <= n; i++) {
        if (t[i] == -1) continue;
        int maxW = t[i];
        //当前沉的这位是t[i],j指针在后面准备给它找一个合适的伙伴,尽量贴近于w
        for (int j = n; j > i; j--) {
            if (t[j] == -1) continue;
            if (t[i] + t[j] <= w) {
                if (t[i] + t[j] > maxW) {
                    maxW = t[i] + t[j];
                    t[i] = -1;
                    t[j] = -1;
                    count++;
                }
            }
        }
        //如果没有人和它进行过配对,自己一船吧
        if (maxW == t[i]) {
            t[i] = -1;
            count++;
        }
    }
    cout << count << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}