排序后用双指针贪心，每次尝试将最便宜和最贵的纪念品配成一组。
OJ: luogu
题目 ID: P1094
难度:普及-
标签:贪心排序双指针python
日期: 2026-07-07 00:00
题意
有 n 件纪念品，每组最多两件，且每组价格和不能超过 w。求最少需要分成多少组。
思路
先看一个小数据暴力：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* date: 2026-07-07 00:00:00
*/
// brute.cpp：小数据暴力解，递归枚举所有分组方式，求最少组数。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int w, n;
int p[MAXN]; // 纪念品价格
int assigned[MAXN]; // assigned[i] = 1 表示第 i 个纪念品已分组
int ans; // 最少组数
// 递归：每次找到第一个未分组的纪念品，决定它的分组方式
void dfs(int cur_groups) {
// 找到第一个未分组的纪念品
int first = -1;
for (int i = 1; i <= n; i++) {
if (!assigned[i]) {
first = i;
break;
}
}
// 全部已分组，更新答案
if (first == -1) {
if (cur_groups < ans) ans = cur_groups;
return;
}
// 剪枝：当前组数已经 >= 当前最优，不继续
if (cur_groups >= ans) return;
// 方案1：first 单独成组
assigned[first] = 1;
dfs(cur_groups + 1);
assigned[first] = 0;
// 方案2：first 和另一个未分组的纪念品配成一组（需满足 p ≤ w）
for (int j = first + 1; j <= n; j++) {
if (!assigned[j] && p[first] + p[j] <= w) {
assigned[first] = 1;
assigned[j] = 1;
dfs(cur_groups + 1);
assigned[first] = 0;
assigned[j] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> w >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
ans = n; // 最多 n 组（每个单独一组）
dfs(0);
cout << ans << '\n';
return 0;
}暴力每次选择第一个未分组物品，枚举它单独一组或和另一个未分组物品配对，复杂度指数级。
正解先排序，然后用双指针：
left指向当前最便宜的纪念品；right指向当前最贵的纪念品；- 如果
prices[left] + prices[right] <= w，把它们放一组； - 否则，最贵的连最便宜的都配不了，只能单独一组。
每轮一定会处理掉当前最贵的纪念品，因此组数加 1。
为什么这样最优？当前最贵物品如果不能和最便宜物品配对，那它不可能和任何其他物品配对，只能单独一组。如果能配对，把最便宜的和它放一起不会浪费更好的机会，因为最便宜物品最容易和别人配，拿来配当前最难处理的最贵物品是安全的。
Python 知识
prices.sort()原地升序排序。- 双指针用
left和right表示当前还没分组的最小/最大物品。 while left <= right覆盖剩一件物品的情况。
代码
python
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
limit = data[0]
n = data[1]
prices = data[2:2 + n]
prices.sort()
left = 0
right = n - 1
answer = 0
while left <= right:
if prices[left] + prices[right] <= limit:
left += 1
right -= 1
answer += 1
print(answer)
if __name__ == "__main__":
main()复杂度
排序复杂度是
空间复杂度是
总结
“每组最多两个、容量有限、组数最少”常用排序双指针。每次先处理最难安置的最大物品。