夏令营7-12贪心学习笔记&总结
贪心
贪心就是在当前条件下的最优解。与DP不同，贪心是保证在当前条件下的最优解。
正常贪心
（我只能用这几个字来和区间区别了）
T1 摩天轮
思路：最大的应该最重与最轻的匹配。如果如果和另一个人匹配，会浪费一些重量。
让凑对的人最多（让座舱最满）
证明正确：假设不是最优，尝试使用不是这个的方法。看看有没有反例。
要从“第一步怎么走”入手。
T2 萨鲁曼的部队
直到要不能满足了再去考虑这个点。
在$[x,x+r]$中找一个点，打一个标记。
T3 小木棍
出了原题错题不可做题而且CSP-J2024也是T3
8用的木棍最多，所以先全选8，位数最小。
在确定了$n-1$位以后，最高位就确定了。
优先让前几位小。总共x位,$x=(\frac{n}{7})向上取整$。
按照$\frac{n}{7}$的余数分类讨
- 位数最少
- 从高往低尽量小。
区间问题
就一句：
$$
全是\huge经典\Huge模板\times N
$$
区间安排问题
按照左端点排序是考虑这样的情况：
考虑逐步开放所有可放的区间，当有区间可以进入时，就进入。相当于找对最后影响最小的区间。即按照右端点排序。
区间选点问题
没有例题先不写
区间覆盖问题1
问题：数轴上有$n$个区间$[L_i,R_i]$，从中选取尽量少的区间覆盖$[x,y]$。
$L$从小到大，$R$从大到小
区间覆盖问题1.2
问题：数轴上有$n$个区间$[L_i,R_i]$，从中选取尽量少的区间覆盖$[x,y]$。区别是这个问题是时段。所以$x=r+1$
区间覆盖问题2
一般的点和区间配对问题
点和区间配对：
所有能和这个点配对的区间中，要选取R的最小值，且能覆盖这个点。因为R大的区间有可能覆盖下一个点。
T7 带区间限制的装箱问题
这题中，可以把盒子当成上一题的点，球当成上一题的区间。
区别是，这里有$10^9$个点，不能逐个枚举，要忽略无用的点。
T8 代金券
$[L_i,1^{9}]（正无穷）$
经典错误：
- $D_i越大越先用$
- $L_i越小越先用$
原则：
- 优先使用优惠大的代金券
- 多用代金券
区间分组问题
T9 牛栏预定（区间分组问题）
把区间分组，每一组的区间两两不相交。
R从往大。L从小往大。
- 取L的最小区间$[L_1,R_1]$
upper_bound$L_2>R_1$- ……，得到1组。
T10 CSP2021-S-1-廊桥分配
这道题的一个关键就是你无法调整飞机靠不靠廊桥，只能控制放几个在国内或国际。飞机是有位置就靠上去，没位置就停在远机位。
对国内区，国际区其实是一样的。
$计算出停靠在国内区i廊桥上的飞机数量C_{1,i}，国际区i号廊桥上的数量C_{2,i}。$
$计算出C_1和c_2的前缀和序列S_1和S_2。$
答案是$max_{0\le i\le n}(s_{1,i}+s_{2,i})$
带反悔的贪心
T13 股票
这题其实有多种解法，这里选择反悔的贪心。
在第$i$天，如果有价值低于$P_i$的股票，就把最便宜的一股买下，但是保留反悔的选项，可以撤消这个行为。
T14 奶牛优惠券
$先买C_i前K小的牛。如果还有钱，以后每次买剩余中的min(C_i+Δ_K,P_i)最小的牛。其中，Δ_K代表了最小优惠。$