跳至正文

1 条题解

  • 0
    @ 2026-10-7 23:01:14

    【本题解由站长编写】

    经典贪心配对:价格排序后用双指针,最贵的物品要么单独一组,要么和最便宜的凑一组(能凑就凑,因为最贵的必须每组一个)。每组数累加即可。n≤30000。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int w, n;
        cin >> w >> n;
        vector<int> p(n);
        for (auto &x : p) cin >> x;
        sort(p.begin(), p.end());
        int i = 0, j = n - 1, groups = 0;
        while (i <= j) {
            if (p[i] + p[j] <= w) i++;
            j--;
            groups++;
        }
        cout << groups << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4307
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者