序理论与微扰贪心

序理论

定义与STL

严格全序

$a \prec b$：连接性，传递性，非对称性

用sort可求出唯一的序列，使得：任取序列前后两元素a，b，有$a \prec b$成立

证明：建图，入度为0的点数始终为1，无环，拓扑序存在

或：m在序列中的位置：$n \prec m$，成立的n的个数+1

弱序

$a \preceq b$：连接性，传递性

注意：存在等价关系：$a\sim b : a \preceq b且b \preceq a$（传递性，对称性）

用sort可求出序列，使得：任取序列前后两元素a，b，有$a \preceq b$成立

且等价元素相邻，交换等价元素，仍是有效的数列

证明：建图，等价元素用一个点表示，点之间用有向边代表各自等价元素的关系，此时图中点的建边关系构成严格全序，沿用之前的证明即可

• Attention：STL的sort自定义序关系需定义成严格全序，等价元素需返回0（否则会越界），其会给出一种可行的序列（具有稳定性）

微扰贪心

做法易想，但严格证明是不显然的

一种可能的类型

求序列$\{a_n\}$使得$f(\{a_n\})$最大

记关系$a \preceq b$为交换序列中相邻的ab，f()不增大（存在等价关系）

最优序列：A：对于其中任意相邻两项有$a \preceq b$成立

若能证明$a \preceq b$是弱序关系（+连接性，传递性），根据上述理论，用sort可求出和A具有相同性质的序列B、

再容易看出：交换等价项，A和B可相互得到，交换时f()不变，故f(A)=f(B)，B亦是最优的序列

Eg: P1080 [NOIP 2012 提高组] 国王游戏

• 题目中的舍弃取整的等价性是不显然的，但直觉表明舍弃是对的
• 排序得到序列A，最优序列是序列B，需注意到B相邻的元素可能没有关系$\preceq$成立，A，B不是通过简单的交换等价项得到的，而是需要构造更复杂的整体max不变的交换方式（可以构造，懒得写了）

？靠感觉：用sort交换相邻项，使所有局部都最优化，盲猜此时全局是最优的