贪心方法与技巧总结
贪心技巧十分重要，在各类比赛中十分常见，
tag:greedy
堆贪心
例题：
P1631 序列合并 - 洛谷
D - Cake 123
按位贪心
例题：
P2431 正妹吃月饼 - 洛谷
反悔贪心
例题：
P14361 社团招新 / club - 洛谷
Exchange Argument
Exchange Argument 指临项交换/交换论证贪心，一种贪心地构造最优序列的思想
tag:sorting,greedy
适用于在一个操作序列中，找到最优的操作顺序
通常会通过定义一个权值比较器，对所有操作按一定标准排序来完成这一过程，通常需要满足下列性质
- 传递性：\(x<y\wedge y<z\Rightarrow x<z\)，由此排序满足全序关系（不满足全序关系编译器可能报
RE，TLE）
- 交换性：\(x<y\Rightarrow y>x\)，保证了排序结果唯一
例题：
P1080 国王游戏 - 洛谷
给定从\(0\)至\(n\)共\(n+1\)个二元组\(\{a_i,b_i\}\)，第\(x\)项的结果\(val_x\)是\(\left\lfloor\frac{\prod_{i=0}^{x-1}a_i}{b_i}\right\rfloor\)，求一种排列方式使得\(\underset{1\le x\le n}{max}val_x\)最小，求这个最小值
考虑相邻两项\(\{a_i,b_i\}\)，\(\{a_{i+1},b_{i+1}\}\)
设前缀积\(Prod\)为
\[P=\prod_{i=0}^{i-1}a_i
\]
则
\[\text{交换前}
\left\{\begin{matrix}
\begin{aligned}
&val_i&=&\left\lfloor\frac{P}{b_i}\right\rfloor\\
&val_{i+1}&=&\left\lfloor\frac{P\times a_i}{b_{i+1}}\right\rfloor
\end{aligned}
\end{matrix}\right.
\ \ \ \
\text{交换后}
\left\{\begin{matrix}
\begin{aligned}
&val_i&=&\left\lfloor\frac{P}{b_{i+1}}\right\rfloor\\
&val_{i+1}&=&\left\lfloor\frac{P\times a_{i+1}}{b_{i}}\right\rfloor
\end{aligned}
\end{matrix}\right.
\]
如果交换更优则一定有
\[\max(\left\lfloor\frac{P}{b_{i+1}}\right\rfloor,\left\lfloor\frac{P\times a_{i+1}}{b_{i}}\right\rfloor)<\max(\left\lfloor\frac{P}{b_i}\right\rfloor,\left\lfloor\frac{P\times a_i}{b_{i+1}}\right\rfloor)
\]
化简得
\[(b_i>a_{i+1}b_{i+1})\vee(b_i<a_{i+1}b_{i+1}\wedge a_ib_i>a_{i+1}b_{i+1})
\]
于是得，当满足下式时需要交换
\[a_ib_i>a_{i+1}b_{i+1}
\]
交换后依题意模拟即可，时间复杂度\(O(nlogn)\)
P3619 魔法 - 洛谷
给定\(n\)个二元组\((t_i,b_i)\)，当且仅当\(T\)严格大于\(t_i\)时能够获取该二元组，\(T\)会加上\(b_i\)，求最多能获取多少个二元组
显然先把\(b\ge 0\)的二元组取完，然后考虑当\(b_i< 0\)时该如何处理，考虑什么时候需要交换顺序，显然满足如下式子则必须交换
\[\left\{\begin{matrix}
T+b_i\le t_{i+1}\\
T+b_{i+1}> t_i
\end{matrix}\right.\Longrightarrow
b_i+t_i<b_{i+1}+t_{i+1}
\]
按题意模拟即可
D - Manga Market
任意两点间移动时间为\(1\)，给定\(n\)个点，每个点有两个参数\(a,b\)，当你在时刻\(t\)到达点\(i\)时，你需要花费\(a_it+b_i\)的时间获得这个点，但如果\(t+a_it+b_i>T+0.5\)你无法获得这个点，求最多能获得的点数
设当前时间点为\(t\)，则当发生如下情况需要交换
\[\begin{aligned}
&\text{交换前}
\left\{\begin{matrix}
\begin{aligned}
&(a_i+1)(t+1)+b_i&<&T+0.5
\\
&(a_{i+1}+1)((a_i+1)(t+1)+b_i+1)+b_{i+1}&>&T+0.5
\end{aligned}
\end{matrix}\right.
\\
&\text{交换后}
\left\{\begin{matrix}
\begin{aligned}
&(a_{i+1}+1)(t+1)+b_{i+1}&<&T+0.5\\
&(a_i+1)((a_{i+1}+1)(t+1)+b_{i+1}+1)+b_i&<&T+0.5
\end{aligned}
\end{matrix}\right.
\end{aligned}
\]
化简得
\[a_{i+1}(b_i+1)>a_i(b_{i+1}+1)
\]
先想如何朴素计算，设\(dp[i][j]\)表示排序后前\(i\)个节点选择\(j\)个的最小时间花费，于是做一个背包，并滚掉一维
\[dp[i]=min(dp[i-1]+a_i(dp[i-1]+1)+b_i,dp[i])
\]
考虑分类讨论，当\(a_i=0\)时，当前点耗费时间为一定值，显然越靠后越优，于是把节点分成两类，对于\(a_i=0\)的所有节点，按\(b\)从小到大排序，记\(sum_i=\sum^i b_i\)，对于每个\(dp[i]\)二分查找最大的\(s_x\)使得\(s_x\le T-dp[i]\)，答案同步更新\(ans=max(ans,x+i)\)
脑电波贪心
例题：
Problem - C - Codeforces
