贪心首先要把问题简单化，不然很难想出贪心策略

P1080 [NOIP2012 提高组] 国王游戏

邻项交换法，考虑将i与i+1交换，是否会更优。

首先相邻两项交换对前后不会有影响。

如果大臣1放在前面，他俩获得的金币数分别为：
    a0/b1,a0*a1/b2
如果大臣2放在前面，他俩获得的金币数分别为：
    a0/b2,a0*a2/b1
首先，我们约去式子里面的a0，然后分别讨论两种情况的最大值，就变成了比较：
    max(1/b1,a1/b2)和max(1/b2,a2/b1)的大小
根据0<a，a是整数的条件，我们可以得出: 
    a1/b2 >= 1/b2、1/b1 <= a2/b1

那么，如果1/b1是最大的，则有
    1/b1>=a2/b1，只可能左右两边相等，则有1/b2<=a2/b1，所以两种情况的最大值是一样的，则不用交换。
同理可得1/b2是最大的情况也不用交换。
那么我们就只要a1/b2和a2/b1的大小就可以了，也就是说如果a1/b2>a2/b1，那么就要交换，变形得：
    a1*b1 > a2*b2
表示要交换，我们排序就只要按照a*b的从小到大排就可以了。

from https://www.luogu.com.cn/blog/yunshu213/guo-wang-you-hu-you-shi-yi-dao-zheng-ming-ti @云殊呀

Buy Low Sell High

反悔堆贪心。先考虑一种策略，前面只要买了股票并且价格比这次小，我们直接在这次卖出。如果这次不卖出，就买入。

可以看出来这个策略非常低能，不能保证这次卖出是最佳的，也不能保证这次买入以后能出手（后面有没有能卖出的时间点要在后面判断）

本身使用堆比较好想到，毕竟一个点要不要卖出要考虑前面的信息。

然后怎么才能用优先队列改造使得这个贪心策略正确呢？我们考虑每次取出之前时间中最低价格，然后如果小于目前价格，就买入加卖出。但是此时卖出不一定最佳，可能之后有价格更高或更优的地方卖出。所以我们这时候【在堆中放入两个当前的价格，并让ans+=x-q.top()】

为什么加入两个呢？之后可能有比当前x更优的y，然后x点卖出了z价买的股票，答案加上了x-z。下一次如果y比x大，则买入了个y-x，而(y-x)+(x-z)就是y-z！然后为什么push两个呢？因为这样相当于直接z买入y卖出了，x点是没用的，所以多push一个以后用。如果push了两个x，连一个都没用上，那就代表x-z是最佳的，多push两个也不会造成影响

[ARC132D] Between Two Binary Strings

考虑每个1一定是与相邻的0交换不然无意义。

然后对于a,b我们找出一一对应的1，a第i个与b第i个对应

1  2
10010
00101
  1 2

然后每个1肯定是在这个范围内挪动，每个位置都可以达到（想想就明白了）

为了让更多1连起来，要把1放在每一段的靠后的位置。如果能与之前连起来，就放在能连起来的位置。

但是被这个卡了

1 1 1 1 0 0
0 1 1 1 1 0

我们会输出第二个，但是正确是第一个

所以我们考虑进行两次上述过程，第一次第一个1我们放在最右侧，第二次我们放在1（前提是L=1），之后就可以了

Burenka and Traditions (hard version)

可以发现不同寻常的一点，每次代价不是1而是r-l+1/2，这给了我们拆分问题的机会

若将操作区间L,R（都异或x都等于0）拆为L,k-1和k,R，也异或x，答案一定不会更劣。所以我们每次只需要进行区间长度为1或2的操作

1,2显然不能重叠，不然1没什么用。然后2直接可以首尾相连连成一长串。

1的话异或自己就成了0，2的话必须异或和为0，一大长串也是如此，所以我们找异或和为0的区间（这样可以两个两个全异或干净了），其余不能这么搞的单独异或。

alexwei大佬写的代码特别简洁：https://www.luogu.com.cn/blog/AlexWei/solution-cf1718a2

P7913 [CSP-S 2021] 廊桥分配

这题太巧妙了，自己想了一个小时还没啥思路，惭愧啊

我的想法是找出一个廊桥最多能让几个飞机停下，然后刨去这些飞机继续进行操作，但这种朴素的思路显然不行。

正解的思路：先假设廊桥无限使用，建两个优先队列，一个是可用的廊桥（1~n），另一个是当前还没有廊桥停的飞机。

首先明确一点：这题是需要排序的，因为飞机是按到达时间进入机场的，所以每个飞机占用廊桥的顺序并非输入而是排序后的顺序。

先把1~n都加入可用廊桥队列，之后从排好序的1~m开始轮流操作（国际国内分开进行）：先把已经起飞的飞机占用的廊桥重新加入队列（也即起飞时间小于当前飞机落地时间），然后如果有空余廊桥就让当前飞机停进去。

这时候就是此解巧妙之处了！这两个优先队列的作用是什么？存飞机的作用很明显是找出起飞时间最靠前的飞机（这样能把已经起飞的飞机重新加入队列），然后廊桥的队列作用呢？假设只有k个廊桥，我们肯定会优先使用前k个，因为优先队列从小到大。在做的同时用res统计每个廊桥能停下的飞机多少（突然感觉跟我一开始想的有一点点类似），最后用res做前缀和，这样res表示的就不是第i个廊桥能停下的飞机，而是有i个廊桥能停下的飞机了。并且如果有k个廊桥，res[k+1]~res[n]就相当于停到远机位了，根本不用考虑。

P2512 [HAOI2008] 糖果传递

好逆天的贪心，这是人能想到的吗？！？

然后求出集合C后，取中位数作为x1即可

这种推式子的贪心我还是第一次见。。。