CQUPT 2025级 数据科学与大数据技术英才班 周测#14
题目目录
| 题号 | 题目 | 主要模型 |
|---|---|---|
| A | P2240 部分背包问题 | 单位价值排序贪心 |
| B | P1208 混合牛奶 | 单价排序贪心 |
| C | P1223 排队接水 | 排序贪心、交换论证 |
| D | P1803 凌乱的 yyy / 线段覆盖 | 区间贪心 |
| E | P3817 小 A 的糖果 | 从左到右局部修正 |
| F | P1090 合并果子 | 优先队列贪心 |
A. P2240 部分背包问题
一、题目大意
有 (N) 堆金币，第 (i) 堆金币：
- 总重量为 (m_i)；
- 总价值为 (v_i)。
背包最多装重量 (T)。
与普通 01 背包不同的是：
每一堆金币都可以任意分割。
也就是说，可以只拿某一堆金币的一部分，并且分割之后单位重量的价值不会改变。
要求求出背包最多能够装走多少价值的金币，答案保留两位小数。
题目中：
[
N\le100,\qquad T\le1000
]
且 (1\le m_i,v_i\le100)。
二、题解前关键信号识别
这道题最重要的一句话不是：
有一个容量有限的背包。
而是：
金币可以任意分割。
如果一个物品可以被拆分，那么我们不再需要纠结：
这一堆到底拿还是不拿？
而应该考虑：
每占用 1 单位背包容量，哪堆金币能带来更多价值？
因此对于第 (i) 堆金币，计算：
[
\frac{v_i}{m_i}
]
也就是：
单位重量价值。
显然，背包容量应该优先留给单位价值更高的金币。
所以第一反应应该是：
计算单位价值↓
按照单位价值从大到小排序↓
依次尽可能多拿
这就是最经典的：
部分背包贪心。
三、数据规模与复杂度判断
(N\le100)，数据规模非常小。
即使进行排序：
[
O(N\log N)
]
也完全没有问题。
排序以后只需要扫描一次：
[
O(N)
]
所以总时间复杂度：
[
O(N\log N)
]
空间复杂度：
[
O(N)
]
为什么不需要动态规划？
如果是 01 背包：
每件物品只能全部拿或者全部不拿。
那么：
单位价值最高
不一定意味着应该优先拿。
但本题允许任意分割。
假设有两堆金币：
A：1 千克价值 10
B：1 千克价值 5
如果背包只剩 0.3 千克容量：
拿 A 的 0.3 千克 → 价值 3
拿 B 的 0.3 千克 → 价值 1.5
无论剩余多少容量，单位价值更高的金币始终更优。
所以可以直接贪心。
四、核心思路
对于每堆金币记录：
m // 总重量
v // 总价值
p // 单位重量价值
其中：
[
p=\frac vm
]
然后按照：
p 从大到小
排序。
情况 1：当前整堆金币都装得下
如果：
m[i]<=T
那么全部装入：
T-=m[i];
ans+=v[i];
情况 2：当前整堆装不下
假设背包还剩：
T
单位价值是：
p[i]
那么可以拿价值：
[
T\times p_i
]
即：
ans+=T*p[i];
背包已经装满，可以结束。
五、参考代码
#include<bits/stdc++.h>
using namespace std;const int N=110;struct Gold
{int m,v;double p;
}a[N];int n,t;bool cmp(Gold x,Gold y)
{return x.p>y.p;
}int main()
{scanf("%d%d",&n,&t);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].m,&a[i].v);a[i].p=1.0*a[i].v/a[i].m;}sort(a+1,a+n+1,cmp);double ans=0;for(int i=1;i<=n;i++){if(t>=a[i].m){t-=a[i].m;ans+=a[i].v;}else{ans+=t*a[i].p;t=0;break;}}printf("%.2lf\n",ans);return 0;
}
六、错因回溯
错误 1：按照总价值排序
例如：
A：重量 100，价值 100
B：重量 1，价值 50
如果只看总价值：
A 更大。
但单位价值：
[
A=1,\qquad B=50
]
显然应该优先拿 B。
因此本题真正比较的是：
单位容量能够带来的收益。
错误 2：按照重量从小到大排序
轻不代表价值高。
例如：
A：重量 1，价值 1
B：重量 2，价值 100
显然不能只因为 A 更轻就优先拿 A。
错误 3：把它当成 01 背包
看到：
背包
容量
价值
就直接想到动态规划，是很常见的惯性思维。
但首先应该检查：
物品能不能分割？
本题明确可以任意分割，因此性质完全不同。
错误 4：整数除法
错误：
a[i].p=a[i].v/a[i].m;
如果：
v=3
m=2
整数除法结果会变成：
1
而不是：
1.5
应该写：
a[i].p=1.0*a[i].v/a[i].m;
七、边界易错点
1. 最后一堆只拿一部分
不能因为整堆放不下就直接跳过。
这恰恰是本题与 01 背包最大的区别。
2. 背包可能装不满所有金币
一旦容量变成 0：
break;
即可。
3. 输出两位小数
printf("%.2lf\n",ans);
4. 即使所有金币都能装下
循环自然会把全部价值累加，不需要特殊处理。
八、下次触发信号
以后看到：
有容量限制
物品可以任意切割
切割以后单位收益不变
应该立刻想到：
单位收益
=
价值 / 消耗
然后：
单位收益最高的优先
核心触发信号：
可以分割 + 容量有限 + 最大化收益 = 按单位价值贪心。
同时要牢记：
部分背包 → 贪心01 背包 → 通常不能这样贪
B. P1208 混合牛奶
一、题目大意
奶制品公司每天需要采购 (n) 单位牛奶。
有 (m) 个奶农，第 (i) 个奶农：
- 每单位牛奶价格为 (p_i)；
- 最多能够提供 (a_i) 单位牛奶。
可以向一个奶农购买：
0 ~ a[i]
之间任意整数数量的牛奶。
题目保证所有奶农总供应量足够满足公司的需求，要求求出满足需求所需要的最小费用。
数据范围中：
[
m\le5000
]
需求量和单个奶农供应量最大为 (2\times10^6)，牛奶单价最大为 1000。
二、题解前关键信号识别
本题最直接的问题是：
同样购买 1 单位牛奶，从谁那里买最划算？
答案显然是：
价格最低的奶农。
因此：
便宜的牛奶
应该尽可能先买。
只有便宜的奶农已经没有牛奶了，才有必要向更贵的奶农购买。
所以：
按单价从小到大排序↓
优先把最便宜的买完↓
再买第二便宜的↓
直到满足需求
三、数据规模与复杂度判断
奶农数量：
[
m\le5000
]
排序复杂度：
[
O(m\log m)
]
之后扫描一次：
[
O(m)
]
因此总复杂度：
[
O(m\log m)
]
空间复杂度：
[
O(m)
]
完全可以接受。
四、核心思路
按牛奶单价：
p[i]
从小到大排序。
定义：
need
表示还需要多少牛奶。
情况 1：当前奶农的牛奶全部需要
如果：
need>=a[i]
那么全部购买：
ans+=1LL*p[i]*a[i];
need-=a[i];
情况 2：只需要当前奶农的一部分
如果：
need<a[i]
只买：
need
单位即可：
ans+=1LL*need*p[i];
need=0;
完成采购。
为什么这样一定最优？
假设当前有：
A 奶农：3 元/单位
B 奶农：5 元/单位
一个方案中出现了：
还有 A 的牛奶可以买
却先购买了 B 的牛奶
那么把购买 B 的一单位牛奶替换成 A：
费用减少 2
而牛奶总量不变。
所以任何最优方案中：
更贵的牛奶被购买之前，所有更便宜且需要的供应都应该先被使用。
因此按价格从低到高购买一定最优。
五、参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int N=5010;struct Farmer
{int p,a;
}f[N];int n,m;bool cmp(Farmer x,Farmer y)
{return x.p<y.p;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d",&f[i].p,&f[i].a);sort(f+1,f+m+1,cmp);LL ans=0;int need=n;for(int i=1;i<=m&&need>0;i++){int buy=min(need,f[i].a);ans+=1LL*buy*f[i].p;need-=buy;}printf("%lld\n",ans);return 0;
}
六、错因回溯
错误 1：按照供应量排序
供应多，并不代表便宜。
假设：
A：1000 单位，10 元
B：10 单位，1 元
即使 B 的供应量很少，也一定应该优先购买。
错误 2：按照总价 p*a 排序
我们可以购买奶农的一部分牛奶。
真正决定每多买一单位牛奶成本的是：
p
而不是：
p*a
错误 3：最后一个奶农也全部买完
公司只要求：
买够 (n) 单位。
如果最后还缺 5 单位，而当前奶农有 100 单位：
只需要买 5
不能把剩下 100 全部购买。
错误 4：费用使用 int
虽然原题范围接近 32 位整数边界，但竞赛中涉及：
数量 × 单价
建议直接使用：
long long
避免乘法中间过程溢出。
七、边界易错点
1. 需求量可能已经是 0
此时答案就是：
0
循环条件：
need>0
可以自然处理。
2. 相同价格顺序无所谓
因为它们的单位成本完全一样。
3. 总供应量足够
题目已经保证可以完成采购。
4. 不需要真的一单位一单位购买
如果奶农能提供 (10^6) 单位牛奶，不应该循环 (10^6) 次。
直接：
buy=min(need,a[i]);
批量计算即可。
八、下次触发信号
看到：
需要购买一定数量
每个来源有不同单价
每个来源有供应上限
可以购买其中任意数量
要求总费用最小
立刻想到：
单价最低
→ 优先尽可能买满
核心触发信号：
同质资源采购 + 不同单价 = 从便宜到贵。
C. P1223 排队接水
一、题目大意
有 (n) 个人排队使用一个水龙头。
第 (i) 个人接水需要：
[
T_i
]
时间。
需要安排一个排队顺序，使所有人的：
平均等待时间最小。
一个人的等待时间不包含他自己的接水时间。
如果两个人接水时间相同，则编号较小的人必须排在前面。
题目中：
[
1\le n\le1000,\qquad 1\le T_i\le10^6
]
并要求输出：
- 排队顺序；
- 最小平均等待时间，保留两位小数。
二、题解前关键信号识别
假设两个人：
A 接水需要 3 分钟
B 接水需要 10 分钟
如果：
A → B
那么：
A 等待 0
B 等待 3
总等待：
[
3
]
如果：
B → A
那么：
B 等待 0
A 等待 10
总等待：
[
10
]
显然：
时间短的人应该排在前面。
因此应该按照：
[
T_i
]
从小到大排序。
这是一类非常经典的：
短任务优先贪心。
三、数据规模与复杂度判断
(n\le1000)。
排序：
[
O(n\log n)
]
扫描计算等待时间：
[
O(n)
]
总复杂度：
[
O(n\log n)
]
空间复杂度：
[
O(n)
]
四、核心思路
为什么短的人应该在前面？
可以使用一个非常重要的贪心证明方法：
交换论证
假设在某个方案中，相邻两个人：
A → B
并且：
[
T_A>T_B
]
设排在他们之前的人总共花了 (S) 时间。
原来的顺序
A 的等待时间：
[
S
]
B 的等待时间：
[
S+T_A
]
两个人贡献：
[
2S+T_A
]
交换之后
变成：
B → A
B 的等待时间：
[
S
]
A 的等待时间：
[
S+T_B
]
贡献：
[
2S+T_B
]
因为：
[
T_B<T_A
]
所以交换以后等待时间更小。
因此只要存在：
前面的人比后面的人慢
就可以交换，并且答案不会变差。
不断交换以后，最终一定得到：
接水时间从小到大
的顺序。
这就证明了贪心策略。
如何计算总等待时间？
排序以后：
t1 t2 t3 ... tn
第一个人等待：
[
0
]
第二个人等待：
[
t_1
]
第三个人等待：
[
t_1+t_2
]
……
可以逐个累加：
sum+=wait;
wait+=t[i];
也可以观察每个人的接水时间会被后面多少个人等待：
第 1 个人影响 n-1 人
第 2 个人影响 n-2 人
...
因此：
[
sum=\sum_{i=1}^{n} T_i(n-i)
]
五、参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int N=1010;struct Person
{int t,id;
}a[N];int n;bool cmp(Person x,Person y)
{if(x.t!=y.t)return x.t<y.t;return x.id<y.id;
}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i].t);a[i].id=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++)printf("%d%c",a[i].id,i==n?'\n':' ');LL sum=0;for(int i=1;i<=n;i++)sum+=1LL*a[i].t*(n-i);printf("%.2lf\n",1.0*sum/n);return 0;
}
六、错因回溯
错误 1：时间长的人先排
有人可能会认为：
先解决最麻烦的人。
但长任务排在前面，会让后面的很多人全部等待这段长时间。
真正希望的是：
尽量减少对后面大量人的阻塞。
所以应该短任务优先。
错误 2：只输出排序后的接水时间
题目第一行要求输出的是：
人的编号。
所以排序时必须保留：
id
不能只存时间。
错误 3：相同时间没有按照编号排序
题目明确规定：
接水时间相同时，编号小的人在前。
因此比较函数必须写：
if(x.t!=y.t)return x.t<y.t;return x.id<y.id;
错误 4：把自己的接水时间算进等待时间
题目说明：
等待时间不包括自己接水的时间。
所以最后一个人的接水时间不会贡献给任何人的等待。
公式中：
a[n].t*(n-n)=0
正好体现这一点。
错误 5：使用 int 保存总等待时间
最坏情况下，总等待时间可以达到很大数量级。
因此：
long long sum;
更加安全。
七、边界易错点
1. (n=1)
只有一个人：
等待时间 = 0
平均等待时间 = 0.00
2. 所有人接水时间相同
必须按照：
1 2 3 ... n
输出。
3. 平均值必须使用浮点除法
不能写：
sum/n
再转成 double。
应该：
1.0*sum/n
4. 输出两位小数
printf("%.2lf\n",...);
八、下次触发信号
以后看到：
一台机器 / 一个窗口
多个人或任务依次处理
后面的任务必须等待前面完成
要求总等待时间或平均等待时间最小
应该想到：
短任务优先。
尤其看到目标函数中：
一个任务越靠前
就会影响越多后面的人
更应该考虑：
让耗时小的任务承担更大的影响次数
核心触发信号：
单机排队 + 最小总等待时间 = 按处理时间升序。
同时记住一个重要证明方法：
贪心顺序不确定时，尝试比较两个相邻元素交换前后的答案。
D. P1803 凌乱的 yyy / 线段覆盖
一、题目大意
有 (n) 场比赛。
第 (i) 场比赛：
- 开始时间为 (a_i)；
- 结束时间为 (b_i)。
如果选择参加一场比赛，就必须完整参加，不能同时参加两场比赛。
要求：
最多能够参加多少场比赛。
题目中：
[
1\le n\le10^6
]
且：
[
0\le a_i<b_i\le10^6
]
数据规模非常大。
二、题解前关键信号识别
这是非常经典的：
区间选择问题。
每场比赛可以表示成一条时间轴上的区间：
[a[i], b[i]]
我们要选择尽可能多的：
两两不冲突的区间。
这时应该思考：
选择当前比赛时，什么条件能够给后面的比赛留下最多机会？
答案是：
结束得越早越好。
例如：
比赛 A：1 → 10
比赛 B：2 → 3
虽然 A 开始更早，但选完 A 后：
直到 10 才能参加下一场。
选 B：
3 就空闲了。
显然 B 为后面的选择留下了更多空间。
因此：
按结束时间从小到大排序。
三、数据规模与复杂度判断
(n\le10^6)。
暴力枚举所有比赛子集：
[
2^n
]
完全不可能。
即使动态规划，如果状态设计复杂，也没有必要。
排序：
[
O(n\log n)
]
之后扫描一次：
[
O(n)
]
总复杂度：
[
O(n\log n)
]
对 (10^6) 规模是合理的。
空间复杂度：
[
O(n)
]
四、核心思路
将所有比赛按照：
结束时间 b
从小到大排序。
定义：
last
表示：
当前最后选择的一场比赛的结束时间。
依次扫描每场比赛。
如果：
a[i]>=last
说明这场比赛开始时，上一场已经结束。
可以参加：
ans++;
last=b[i];
否则：
当前比赛与已经选择的最后一场冲突
直接跳过。
为什么结束时间最早一定最好？
假设现在可以选择：
A：结束时间 5
B：结束时间 8
并且两场都能接在当前方案后面。
如果选择 A：
5 之后可以继续选择。
如果选择 B：
8 之后才能继续选择。
所有在：
8 以后
能参加的比赛，在：
5 以后
也同样可以参加。
而选择 A 还可能额外参加开始时间在：
[5,8)
之间的比赛。
因此：
选择结束时间更早的比赛绝不会让未来变差。
五、参考代码
#include<bits/stdc++.h>
using namespace std;const int N=1000010;struct Match
{int l,r;
}a[N];int n;bool cmp(Match x,Match y)
{return x.r<y.r;
}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+n+1,cmp);int ans=0;int last=-1;for(int i=1;i<=n;i++){if(a[i].l>=last){ans++;last=a[i].r;}}printf("%d\n",ans);return 0;
}
六、错因回溯
错误 1：按照开始时间最早排序
开始得早并没有价值。
例如：
A：0 → 100
B：1 → 2
C：2 → 3
D：3 → 4
如果先选 A：
只能参加 1 场。
而：
B → C → D
可以参加 3 场。
错误 2：优先选择持续时间最短的比赛
持续时间短也不一定最好。
例如：
A：10 → 12
虽然只持续 2 个单位时间，但可能结束得很晚。
我们真正关心的是：
从什么时候开始重新获得选择自由。
所以应该看：
结束时间
而不是：
区间长度
错误 3：判断条件写成 >
如果：
上一场结束时间 = 5
下一场开始时间 = 5
两场并不重叠。
所以可以连续参加。
应该写：
a[i].l>=last
而不是：
a[i].l>last
错误 4：选择了比赛却没有更新 last
只有真正参加了当前比赛时：
last=a[i].r;
未选择的比赛不能影响后面的判断。
七、边界易错点
1. (n) 高达 (10^6)
数组必须开够：
const int N=1000010;
2. 起始时间可以是 0
因此如果使用：
last=0;
也是可以的。
参考代码使用：
last=-1;
更加直观地表示“当前没有参加任何比赛”。
3. 相同结束时间
无论先处理哪一个，只要按照结束时间不降排列，贪心性质不会被破坏。
4. 只要求数量
不需要保存具体选择了哪些比赛。
八、下次触发信号
看到：
很多时间区间
选择的区间不能重叠
要求选择数量最多
应当马上想到经典区间贪心：
按结束时间升序↓
能选就选
核心触发信号：
最多选择互不相交区间 = 优先结束最早。
要区分几个常见问题：
最多选择不相交区间
→ 按结束时间合并区间
→ 通常按开始时间区间覆盖
→ 又是另一类贪心
不能看到“区间”两个字就套同一个模板。
E. P3817 小 A 的糖果
一、题目大意
有 (n) 个糖果盒。
第 (i) 个盒子中有：
[
a_i
]
颗糖。
每次可以从任意一个盒子中吃掉一颗糖。
要求最终满足：
[
a_i+a_{i+1}\le x
]
对所有相邻糖果盒都成立。
求：
最少需要吃掉多少颗糖。
题目中：
[
2\le n\le10^5
]
并且：
[
0\le a_i,x\le10^9
]
因此最终答案需要注意整数范围。
二、题解前关键信号识别
这道题没有：
排序
也没有明显的：
最大值 / 最小值选择
所以初学者很容易看不出它是贪心。
关键在于观察限制：
[
a_i+a_{i+1}\le x
]
这是一个：
只涉及相邻两个位置的局部限制。
可以从左到右依次处理。
当处理到：
a[i-1] 和 a[i]
时，前面的：
a[1] ... a[i-1]
已经全部处理完毕。
如果当前：
[
a_{i-1}+a_i>x
]
必须吃掉：
[
a_{i-1}+a_i-x
]
颗糖。
问题是：
应该从左边盒子吃，还是从右边盒子吃？
应该尽量：
只修改当前的右边盒子 (a_i)。
因为左边的 (a_{i-1}) 已经和：
a[i-2]
共同满足了前一个条件。
回头修改它没有任何额外好处。
三、数据规模与复杂度判断
(n\le10^5)。
如果尝试搜索：
每颗糖到底从哪个盒子吃
显然不可行。
但由于约束只和相邻位置有关，可以从左到右一次解决。
时间复杂度：
[
O(n)
]
空间复杂度：
[
O(n)
]
甚至可以优化到：
[
O(1)
]
额外空间。
四、核心思路
为了让处理方式统一，可以人为定义：
a[0]=0;
然后从：
i=1
开始处理。
每次检查：
[
a_{i-1}+a_i
]
如果没有超过 (x)
if(a[i-1]+a[i]<=x)
什么都不需要做。
如果超过 (x)
超出的数量：
[
d=a_{i-1}+a_i-x
]
必须至少吃掉这么多颗糖。
我们直接从：
当前盒子 a[i]
中吃掉：
a[i]-=d;
答案：
ans+=d;
为什么需要先处理 a[1]？
考虑：
a1=10
a2=0
x=5
如果直接从：
a1+a2
开始，并要求只修改 a2：
需要吃 5
但 a2 本来只有 0
就出问题了。
所以设置：
a[0]=0;
首先检查：
[
a_0+a_1\le x
]
实际上就是保证：
[
a_1\le x
]
如果 a1>x：
先把 a1 减到 x。
这样之后每一步的超出量都一定可以从当前 a[i] 中扣除。
为什么从右边吃一定最优？
处理：
a[i-1] + a[i]
时：
a[i-1]
已经被确定。
因为：
a[i-2]+a[i-1]<=x
已经满足。
现在当前这一对超出了 d。
无论如何：
至少都必须吃掉 (d) 颗。
我们恰好吃掉：
d
颗，所以当前操作数量已经是最少可能值。
并且全部从 a[i] 中吃还有一个好处：
a[i]越小，下一组a[i]+a[i+1]越容易满足。
因此不会对未来造成坏影响。
五、参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int N=100010;int n;
LL x,a[N];int main()
{scanf("%d%lld",&n,&x);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);a[0]=0;LL ans=0;for(int i=1;i<=n;i++){if(a[i-1]+a[i]>x){LL d=a[i-1]+a[i]-x;ans+=d;a[i]-=d;}}printf("%lld\n",ans);return 0;
}
六、错因回溯
错误 1：只从 i=2 开始
例如：
n=2
x=510 0
如果直接处理：
a1+a2
并试图全部从 a2 吃：
a2 会变成负数。
所以首先需要处理：
a1>x
的情况。
使用：
a[0]=0;
可以把这个边界统一进普通循环。
错误 2：超出以后从左边盒子吃
处理到第 (i) 个位置时：
a[i-1]
已经参与并满足了前一个限制。
如果继续修改左边：
虽然不会破坏前面的“不超过 x”，但对于下一组约束没有任何帮助。
而减少：
a[i]
既解决当前问题，又能帮助：
a[i]+a[i+1]
这一组。
所以应该修改右边。
错误 3：一次只吃一颗糖进行模拟
假设超出：
1000000000
颗。
如果一颗一颗吃：
while(...)
{a[i]--;ans++;
}
复杂度可能极高。
直接计算：
d=a[i-1]+a[i]-x;
一次处理完即可。
错误 4：修改了答案但没有修改数组
例如：
ans+=d;
却忘记：
a[i]-=d;
那么处理下一对：
a[i]+a[i+1]
时仍然使用原来的糖果数量，会重复计算。
错误 5：答案使用 int
(n\le10^5)，单个 (a_i\le10^9)。
累计吃掉的糖果数量可能明显超过普通 32 位整数范围，因此应该使用：
long long
七、边界易错点
1. (x=0)
最终所有相邻盒子之和都必须为 0。
参考代码仍然可以正常处理。
2. 原序列已经全部合法
每一步：
a[i-1]+a[i]<=x
答案自然为 0。
3. 第一盒本身大于 (x)
必须先降低第一盒。
a[0]=0 可以自然完成这件事。
4. 修改后的 a[i] 要继续参与下一次判断
这正是贪心过程的一部分。
八、下次触发信号
以后看到：
对相邻位置有限制
可以通过减少、增加或修改当前位置解决冲突
前面的状态一旦处理好就不需要再回头
应该尝试：
从左到右扫描↓
发现当前局部不合法↓
用最小代价把它刚好修到合法↓
继续处理后面
核心触发信号：
局部相邻约束 + 修改具有单向影响 = 从左到右局部修正贪心。
这道题也特别说明：
贪心不等于排序。
贪心真正的本质是：
每一步做一个可以证明“不比其他选择差”的局部决策。
F. P1090 合并果子
一、题目大意
有 (n) 堆果子，第 (i) 堆有：
[
a_i
]
个果子。
每次可以选择两堆果子进行合并。
假设选择的两堆大小分别为：
[
x,\ y
]
那么：
- 产生一堆大小为 (x+y) 的新果子；
- 本次合并消耗体力：
[
x+y
]
不断进行合并，直到最终只剩下一堆。
要求：
最小化所有合并操作的总体力消耗。
题目中：
[
1\le n\le10^4
]
每堆果子数量：
[
1\le a_i\le2\times10^4
]
题目保证最终答案小于 (2^{31})。
二、题解前关键信号识别
最重要的观察是：
一堆果子一旦被合并形成新堆，之后还有可能继续参与后面的合并。
也就是说：
越早合并进去的重量，会被重复计算越多次。
例如：
1 2 9
如果先合并：
1+2=3
花费：
3
再：
3+9=12
总花费：
[
3+12=15
]
而如果先：
2+9=11
再：
1+11=12
总花费：
[
11+12=23
]
明显更大。
因此：
那些会被重复计算多次的果子，应该尽可能轻。
所以每次应该：
选择当前最小的两堆果子进行合并。
三、数据规模与复杂度判断
如果每次都：
遍历数组找最小的两堆
一次需要：
[
O(n)
]
一共要合并：
[
n-1
]
次。
复杂度：
[
O(n^2)
]
对于本题 (n=10^4) 虽然部分情况下可能勉强，但并不是合理实现。
我们需要一种数据结构支持：
快速取出最小元素
插入新元素
这正是：
小根堆 / 优先队列。
每次：
取两个最小值：O(log n)
插入新值：O(log n)
总共进行 (n-1) 次。
时间复杂度：
[
O(n\log n)
]
空间复杂度：
[
O(n)
]
四、核心思路
使用小根堆：
priority_queue<int,vector<int>,greater<int> > q;
将所有果子堆加入优先队列。
然后不断进行：
取出最小的一堆 x
取出第二小的一堆 y合并：
z=x+y答案：
ans+=z新果堆：
把 z 重新放入优先队列
直到：
优先队列只剩一个元素。
为什么一定选择最小的两堆？
可以从“每个原始果子会被计算多少次”理解。
最终的合并过程可以看成一棵二叉树：
总果堆/ \... ...
叶子是最开始的每一堆果子。
某一堆果子位于树中越深：
它的重量就会在合并费用中被重复计算越多次。
因此我们希望：
重量大的果堆
→ 尽量浅重量小的果堆
→ 可以更深
而每次选择最小的两堆合并，正是在构造满足这个性质的最优合并树。
这就是经典的：
Huffman 贪心思想。
一个更直观的理解
假设当前有：
[
a\le b\le c
]
无论如何，至少有两堆需要先合并。
如果先让大的 (c) 参与合并：
c
就会提前进入新果堆，并在以后再次被计算。
而选择：
a 和 b
可以让重复参与后续合并的重量尽量小。
因此应该合并最小两堆。
五、参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;int n;priority_queue<int,vector<int>,greater<int> > q;int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);q.push(x);}LL ans=0;while(q.size()>1){int x=q.top();q.pop();int y=q.top();q.pop();int z=x+y;ans+=z;q.push(z);}printf("%lld\n",ans);return 0;
}
六、错因回溯
错误 1：每次选择最大的两堆
大的果堆如果过早参与合并：
后续每次合并都会再次计算这部分大重量。
所以通常会造成很高的总代价。
本题恰好应该反过来：
小的尽早合并
大的尽量晚参与
错误 2：只排序一次，然后依次合并
例如初始：
1 2 3 100
第一次：
1+2=3
产生了一堆新的：
3
现在所有果堆变成：
3 3 100
下一次应该重新选择：
3 和 3
所以：
新产生的果堆必须重新参与“找最小值”。
只对原数组排序一次，然后机械地从左往右处理是不够的。
错误 3：合并后没有把新果堆放回去
合并：
x+y
以后，新果堆还必须参与后续合并。
因此：
q.push(x+y);
不能漏。
错误 4：循环次数写成 n
(n) 堆果子最终合成 1 堆，只需要：
[
n-1
]
次合并。
最自然的判断方式不是手动数次数，而是：
while(q.size()>1)
错误 5：不会写小根堆
C++ 默认：
priority_queue<int> q;
是：
大根堆。
每次 top() 得到最大值。
本题需要最小值，所以应该写：
priority_queue<int,vector<int>,greater<int>
> q;
七、边界易错点
1. (n=1)
只有一堆果子：
根本不需要合并
答案：
0
此时：
while(q.size()>1)
一次也不会执行。
2. 新果堆可能比原来的很多果堆更小
所以一定要重新加入小根堆，而不能简单追加到固定顺序中。
3. 答案建议使用 long long
虽然原题保证答案小于 (2^{31})， 但这种“多次累加合并代价”的题目养成使用：
long long
的习惯更安全。
4. 每次必须取两个不同的堆
因此是：
top → pop
top → pop
然后再合并。
八、下次触发信号
以后看到：
有很多堆 / 文件 / 木板 / 节点
每次合并两个
合并代价等于两者之和
合并后的新对象还会继续参与合并
要求所有合并总代价最小
应该立刻想到：
每次取当前最小的两个↓
合并↓
重新放回
对应数据结构：
小根堆
核心触发信号：
反复合并 + 代价为两者之和 + 求总代价最小 = Huffman 贪心。
六道题的知识递进
这六道题放在一起，可以形成一条比较完整的贪心入门路线。
第一层：最直观的“优先选更赚的”
P2240 部分背包问题
单位容量有限↓
比较单位价值↓
单位价值高的优先
核心：
收益 / 成本。
第二层：最直观的“优先选更便宜的”
P1208 混合牛奶
需要固定数量资源↓
不同来源价格不同↓
便宜的先买
核心：
成本低的资源优先使用。
第三层：开始学习证明贪心
P1223 排队接水
谁应该排前面？↓
比较相邻两个任务↓
交换顺序↓
短任务在前更优
核心：
交换论证。
这一步非常重要。
从这题以后不能只满足于：
“我感觉这样贪应该对。”
而应该开始问：
为什么这样贪一定不会更差？
第四层：经典区间贪心
P1803 凌乱的 yyy
很多互相冲突的区间↓
希望选择最多↓
给未来留下最多空间↓
优先结束最早
核心：
当前选择要尽量少限制未来。
第五层：认识“贪心不一定排序”
P3817 小 A 的糖果
相邻位置出现冲突↓
从左到右处理↓
每次只做必须做的最小修改
核心：
局部约束 + 单向扫描。
第六层：动态维护当前最优选择
P1090 合并果子
当前最小两个↓
合并产生新元素↓
新元素重新参与选择
因此普通排序已经不够，需要：
优先队列
核心：
每一步都要动态找到当前最优对象。
贪心题的完整思考流程
与 DFS、BFS 不同，贪心通常没有一个固定模板。
真正困难的是：
怎么发现贪心策略，以及怎么证明它。
做题时可以按照下面的顺序思考。
1. 题目要求最大化还是最小化什么？
先明确目标函数：
最大价值
最小费用
最小等待时间
最多区间
最少修改次数
最小合并代价
不要一上来就考虑代码。
2. 当前有哪几种选择？
例如：
P2240
当前容量给哪堆金币？
P1223
谁排在前面？
P1803
当前选择哪一个区间？
P1090
当前合并哪两堆？
贪心就是要回答：
当前这一步应该选谁？
3. 有没有明显的排序依据？
常见排序关键字：
单位价值
价格
处理时间
结束时间
起始时间
截止时间
重量
但不要认为：
贪心 = sort。
P3817 就完全不需要排序。
4. 当前选择会怎样影响未来？
这是非常重要的问题。
例如 P1803：
当前比赛结束越晚
→ 后面能参加的比赛越少
所以应该：
结束越早越好。
P1090：
越早合并进去的重量
→ 后面会被重复计算越多次
所以应该：
轻的尽量早点合并。
5. 能不能用交换论证？
如果问题涉及：
排列顺序
处理顺序
选择顺序
可以尝试：
假设最优方案中有两个相邻元素不符合我的贪心规则，把它们交换会怎样？
如果交换后：
答案不会变差
就说明可以不断交换，直到形成贪心顺序。
代表题：
P1223 排队接水
6. 能不能证明“当前选择不会限制未来”？
例如 P1803：
选择结束时间最早的比赛以后：
任何选择结束更晚比赛之后能够完成的后续方案，它都同样可以完成。
所以：
结束最早
不会比其他选择差。
7. 是否每一步只需要“刚好修复”当前问题？
例如 P3817：
当前超出：
[
d
]
那么：
至少必须吃 d 颗
我们恰好：
吃 d 颗
既不少，也不多。
这种：
每一步只支付不可避免的最低代价
也是很常见的贪心信号。
8. 最优对象会不会动态变化？
如果只排序一次就足够：
P2240
P1208
P1223
P1803
普通：
sort
即可。
如果操作以后会产生新的候选：
P1090
就需要：
priority_queue
动态维护最优元素。
六道题最终触发信号总结
| 题目 | 看到什么 | 应触发什么 |
|---|---|---|
| P2240 | 可以分割、容量有限、最大价值 | 单位价值最高优先 |
| P1208 | 固定需求、不同单价、供应有限 | 最便宜优先购买 |
| P1223 | 单窗口排队、最小等待时间 | 短任务优先 |
| P1803 | 最多选择互不重叠区间 | 结束最早优先 |
| P3817 | 相邻限制、允许减少、从左向右 | 局部刚好修复 |
| P1090 | 两两合并、代价为和、新对象继续参与 | 每次合并最小两项 |
最后：怎样判断一道题可能是贪心？
贪心题经常具有这样的特点：
问题规模很大
↓
暴力搜索不可能状态很多
↓
完整 DP 又显得过重但每一步似乎存在一个
“永远不会吃亏”的选择
这时不要直接凭感觉写代码，而应该继续问：
1. 我的局部最优策略到底是什么？2. 为什么选它不会让未来变差？3. 如果不这样选，能不能把某个最优方案调整成这样？4. 调整之后答案是否不会变差？5. 是否存在反例能够击穿我的策略？
尤其应该学会三种最基础的贪心证明思维：
交换论证↓
把“不符合贪心顺序”的两个对象交换替换论证↓
把最优方案中的某个选择替换成贪心选择局部必要代价↓
证明当前至少必须付出这么多，
而我们的方案恰好只付出这么多
对应到本场比赛：
P2240 / P1208
→ 替换思想P1223
→ 交换论证P1803
→ 不限制未来 / 替换思想P3817
→ 局部必要代价P1090
→ 最小元素优先参与重复代价
当做贪心题时开始主动寻找：
“为什么这个选择永远不会比其他选择差？”
而不是只记住：
sort(...)
才算真正开始掌握贪心。