8030 纪念品分组
大约 4 分钟贪心
8030 纪念品分组
【算法标签】 贪心
【语法标签】 :数组、sort、while循环、for循环、cin/cout
元旦快到了,乐乐负责新年晚会的纪念品发放。他要把购来的纪念品根据价格进行分组,规则是:
- 每组最多两件纪念品
- 每组纪念品的价格之和不能超过
求:最少的分组数目。
数据范围:
- 每组价格上限 为整数
- 纪念品总件数 (题目中为 ,)
- 每件纪念品价格 ,满足
输入格式:
w // 每组价格上限
n // 纪念品件数
P1 // 第1件价格
P2 // 第2件价格
...
Pn // 第n件价格样例:
输入: 输出:
100 6
9
90
20
20
30
50
60
70
80
90样例解释:9 件纪念品,价格上限 100。排序后为 [20, 20, 30, 50, 60, 70, 80, 90, 90]。最少分 6 组。
二、解题思路
数据规模分析
题目来自 NOIP 2007 普及组, 最大约 。 的排序 + 的贪心扫描完全可行。
贪心策略
核心思想:排序 + 双指针,大带小。
- 将纪念品按价格从小到大排序
- 设左指针 指向最便宜的,右指针 指向最贵的
- 每次看最便宜的 + 最贵的:
- 如果 :配对成功, 右移, 左移
- 如果 :最贵的太大,没人能跟它配,它单独一组, 左移
- 每走一步,答案
- 当 时结束
为什么贪心是正确的?
考虑最贵的纪念品 :
- 如果最便宜的 都跟它配对不了(),那没有任何纪念品能跟它配对,它必须单独一组。
- 如果最便宜的能跟它配对(),把它们配在一起一定不差——因为把便宜的"搭"给贵的,既能处理掉最难配的贵的,也能消耗一个便宜的,一举两得。如果不用这个便宜的配对,把它留给别的贵的,结果不会更好。
这就是经典的"大带小"策略。
手动模拟样例
排序后的数组:[20, 20, 30, 50, 60, 70, 80, 90, 90]
| 步骤 | 和 | 判断 | 操作 | 组数 | ||||
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 9 | 20 | 90 | 110 | >100 | 90 单独,-- | 1 |
| 2 | 1 | 8 | 20 | 90 | 110 | >100 | 90 单独,-- | 2 |
| 3 | 1 | 7 | 20 | 80 | 100 | ≤100 | 配对,++, -- | 3 |
| 4 | 2 | 6 | 20 | 70 | 90 | ≤100 | 配对,++, -- | 4 |
| 5 | 3 | 5 | 30 | 60 | 90 | ≤100 | 配对,++, -- | 5 |
| 6 | 4 | 4 | 50 | 50 | — | 剩一个单独 | 6 |
结果:6 组,与样例输出一致。
分组情况:
- 组 1:90(单独)
- 组 2:90(单独)
- 组 3:20 + 80
- 组 4:20 + 70
- 组 5:30 + 60
- 组 6:50(单独)
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int a[N];
int main() {
int w, n;
cin >> w >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 按价格从小到大排序
sort(a + 1, a + n + 1);
int l = 1, r = n; // 双指针:左指向最便宜,右指向最贵
int ans = 0; // 分组数
while (l <= r) {
if (l == r) { // 只剩一个,单独一组
ans++;
break;
}
if (a[l] + a[r] <= w) { // 可以配对:大带小
l++;
r--;
} else { // 最贵的太大,单独一组
r--;
}
ans++;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。排序占主导,双指针扫描仅 。
- 空间复杂度:。需要数组存储所有纪念品价格。
五、知识扩展
双指针的适用场景
双指针技巧在贪心问题中很常见,通常需要满足:
- 数组已排序
- 两个指针分别从两端向中间移动
- 每次移动有一个明确的贪心决策
与 "合并果子" 的区别
| 纪念品分组 | 合并果子 | |
|---|---|---|
| 每组限制 | 最多 2 件 | 无限制 |
| 目标 | 最少组数 | 最小合并代价 |
| 策略 | 双指针配对 | 优先队列取最小 |
| 复杂度 |
易错点
- 排序方向:从小到大排序,不要弄反。
- 等于号的判断: 时可以配对( 不是 ),等于上限也能配。
- 单件成组:当 时还剩一件,不要忘记给它也计一组!
- 不要漏读输入:输入格式中 和 在不同行,纪念品价格也是每行一个。
