2022 简思短解
P1080 [NOIP2012 提高组] 国王游戏
结论：将大臣按照 \(a\times b\) 升序排序求答案（要高精度）即可。
证明（排序贪心证明模板）：如果有一个大臣序列 \(p'\) 比按照 \(a\times b\) 排序的 \(p\) 要优。考虑 \(p'\) 冒泡排序至 \(p\) 的过程，对于一次邻项逆序对，下一段证明答案不劣，通过连不等式得 \(p\) 不比 \(p'\) 劣，而 \(p'\) 比 \(p\) 优，矛盾，得 \(p\) 取到最优解。
若 \(a_i\times b_i>a_{i+1}\times b_{i+1}\)，则 \(\max\{\dfrac{1}{b_i},\dfrac{a_i}{b_{i+1}}\}>\max\{\dfrac{1}{b_{i+1}},\dfrac{a_{i+1}}{b_i}\}\) 也就是说 \(i,i+1\) 交换不会让获得奖赏更多的大臣出现，即不劣。
273. 分级/CF713C Sonya and Problem Wihtout a Legend/CF13C Sequence/P2893 [USACO08FEB]Making the Grade G/P4331 [BalticOI 2004]Sequence 数字序列/P4597 序列 sequence/P8118 Mystery
Submissions：273. 分级 | CF713C Sonya and Problem Wihtout a Legend | CF13C Sequence | P2893 [USACO08FEB]Making the Grade G | P4331 [BalticOI 2004]Sequence 数字序列 | P4597 序列 sequence | P8118 Mystery
千万题目汇成一句话：给定长度为 \(N(\le 10^6)\) 的序列 \(A\)，构造一个长度为 \(N\) 的非降序列 \(B\)，最小化 \(S=\sum\limits^N_{i=1}|A_i?B_i|\)，求出 \(S\) 的最小值和 \(B\) 的构造方案。
其实上面部分题目的 \(N\) 没这么大，\(O(N^2)\) Dp 能过。
先说 Dp，\(f[i][j]\) 表示前 \(i\) 个数字，其中最后一个数字 \(\le j\)，最优答案是多少。
考虑转移，分两步：
-
\(f[i][j] = f[i-1][j] + |a[i] - j|\)
-
\(f[i][j] = \min\{f[i][j],f[i][j-1]\}\)
接下来考虑优化：
如果我们得到这个 Dp 数组，用一般的方法就可以倒着推回去得到方案。
其实 \(f[i][j]\)（看作关于 \(j\) 的函数）是一个斜率单调以 \(1\) 递减的折线，我们只需要知道拐点就可以了。
本人想法：
考虑加入一个绝对值函数，如果在之前斜率为 \(0\) 的直线上，相当于这个左边斜率减一，否则相当于右边的斜率都加一（这时候斜率为为 \(-1\) 的就没啦，和右边并起来了）。
我们用堆来维护折线的拐点的横坐标即可。
更人话的解读：
考虑元素依次加入序列，若是单调非降的，那没问题，\(b_i=a_i\) 即可。若一个 \(i\) 使得 \(b_i\) 不是 \(b_{[1,\dots,i]}\) 的最大值，那么将前缀最大的 \(b_j\)“拖下水”，即和 \(b_i\) 一样赋值为 \(a_i\)（因为要满足 \(B\) 的单调性，这时代价 \(b_j-a_i\) 为最优方案）。
你可能会说，这样会有问题，如下图：
\(z\) 不就 \(>y\) 了（不满足单调性）了吗？
\(x,y\) 拖下水后，我们将她们俩暂时抹上一缕灰色。如果到最后 \(z\) 被拖到比 \(x,y\) 还要深的水里，那就满足了；如果到最后 \(z\) 仍然比 \(x\) 要大，那么 \(x,y\) 永远不会再被拖下水，因为前面总有比她们大的 \(z\) 顶风。最后 \(x,y\) 一起上升到 \(z\) 的高度（一定不比原始的 \(y\) 高），这样代价不变，仍满足要求。
维护前缀最大值用大顶堆。
或者再换一种说法。考虑下面一种想法（主要是我想不到怎么正向考虑这种诡异的想法，只能强行说明这个做法的正确性）：
我们边维护序列边用优先队列维护当前修改过的序列的最大值，每当我们得到一个数 \(x\)，我们先把它加入优先队列，然后取出堆顶 \(y\)（如果有多个最大值，我们取出靠后的），如果 \(x\ge y\)，我们不用管，如果 \(x
我们考虑任意一种调整方法,发现对于逆序对 \(x,y(x
然后考虑一个问题：如果 \(y\) 修改为 \(x\) 之后，\(y\) 前面的最大值 \(z\) 大于 \(y\) 了（即 \(x
我们构造到最后，这个 \(z\) 有可能也被修改了，我们不妨讨论 \(z\) 最终的值 \(z'\)。
我们定义“微调”为不改变花费的情况下，改变某个数对的值。
如果 \(z'>x\)，那么我们可以强行把 \(x\) 和 \(y\) 强行微调成 \(z'\)（考虑正确性：因为 \(x
如果 \(z'\le x\)，那么我们发现它与 \(x\) 和 \(y\) 不再存在矛盾，而它之前的数与它的矛盾可以用类似归纳法一样的方式证明微调可以使得花费不变。
时间复杂度：\(O(n\log n)\)。
int n,x,ans=0,b[N];
priority_queue q;
int main(){
cin>>n;
For(i,1,n){
cin>>x;
q.push(x);
if(q.top()!=x){
ans+=q.top()-x;
q.pop();
q.push(x);
}
b[i]=q.top();
}
Rof(i,n-1,1) ckmn(b[i],b[i+1]);
cout<