8030 【07NOIP普及组】纪念品分组
大约 3 分钟
8030 【07NOIP普及组】纪念品分组
【算法】 贪心、排序、双指针
【C++】 sort、双指针、贪心
【难度】 普及-
一、题目简述
有 件纪念品,要分成若干组。每组最多 2 件纪念品,且每组纪念品的价格之和不能超过给定的上限 。求最少能分成多少组。
数据范围:,,每件纪念品的价格 满足 。
简单来说:把一堆数字两两配对(或单独一个),要求每对的和不超过 ,问最少配出多少对/组。
二、解题思路
算法选择:贪心 + 双指针
这是一个经典的贪心问题。直觉是:最贵的纪念品要和最便宜的纪念品尝试配对。
- 如果最贵的和最便宜的都不能配对(即它们的和 > ),那么最贵的这件只能自己一组。
- 如果最贵的和最便宜的能配对(即它们的和 ≤ ),那么就把它俩分在一组 —— 这样不会"浪费"便宜的纪念品(因为便宜的无论如何都容易和别人配对,但贵的却很难配对,所以应该优先让贵的带走一个便宜的)。
这个贪心策略是正确的,因为:最贵的物品最难配对,如果它连最便宜的都无法配对,那它和任何人都配不了,只能单组;如果能配对,那带走最便宜的是最优的,因为便宜的和谁配都行,不如帮贵的"脱困"。
具体实现
- 将 件纪念品的价格从小到大排序。
- 用双指针 指向最左端(最便宜), 指向最右端(最贵)。
- 当 时循环:
- 如果
a[l] + a[r] <= w:两人一组,l++, r-- - 否则:最贵的单独一组,
r-- - 每次
cnt++(分出一组)
- 如果
- 输出
cnt。
手动模拟
以 ,,价格数组为 [90, 20, 20, 30, 50, 60, 70, 80, 90] 为例。
首先排序:[20, 20, 30, 50, 60, 70, 80, 90, 90]
| 步骤 | l | r | a[l] | a[r] | 和 | 判断 | 操作 | cnt |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 20 | 90 | 110 > 100 | 90 单独 | r-- | 1 |
| 2 | 0 | 7 | 20 | 90 | 110 > 100 | 90 单独 | r-- | 2 |
| 3 | 0 | 6 | 20 | 80 | 100 ≤ 100 | 配对 | l++, r-- | 3 |
| 4 | 1 | 5 | 20 | 70 | 90 ≤ 100 | 配对 | l++, r-- | 4 |
| 5 | 2 | 4 | 30 | 60 | 90 ≤ 100 | 配对 | l++, r-- | 5 |
| 6 | 3 | 3 | 50 | 50 | — | l=r 单独 | — | 6 |
结果:最少 6 组。
三、参考代码
#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 = 0; i < n; i++) cin >> a[i];
sort(a, a + n); // 从小到大排序
int l = 0, r = n - 1, cnt = 0;
while (l <= r) {
if (a[l] + a[r] <= w) {
// 最便宜的 + 最贵的可以一组
l++;
r--;
} else {
// 最贵的单独一组
r--;
}
cnt++; // 无论如何都会分出一组
}
cout << cnt << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,主要耗时在排序。双指针扫描为 。
- 空间复杂度:,存储价格数组。
易错点
- 循环条件必须是
l <= r,当 时还剩一个元素需要单独成组,不能漏掉。 - 价格可能有重复值(如示例中有两个 20 和两个 90),排序后双指针依然正确。
- 注意数组下标可以从 0 开始会更方便(配合
sort(a, a + n))。
