1 条题解
-
0
【本题解由站长编写】
经典贪心配对:价格排序后用双指针,最贵的物品要么单独一组,要么和最便宜的凑一组(能凑就凑,因为最贵的必须每组一个)。每组数累加即可。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
- 上传者