贪心 - 排序

Luogu P3619

对于 $b_i\ge 0$，由于 $T$ 是非严格递增的，所以直接按照 $t_i$ 升序排序即可。

对于 $b_i<0$，此时 $T$ 是严格递减的。我们不能仅通过 $t_i$ 的关系排序，因为可能存在一个很小的 $t_i$ 使 $T$ 减得很多，也可能存在一个很大的 $t_i$ 使 $T$ 减得很小。

如果对于所有的不合法的相邻两项 $(t_i,b_i),(t_{i+1},b_{i+1})$ 通过交换后合法，那么有：

$$T+b_i\le t_{i+1}\\ T+b_{i+1}>t_i$$

那么会导出 $t_i-b_{i+1}<T\le t_{i+1}-b_i$，因此一定会有 $t_i+b_i<t_{i+1}+b_{i+1}$。

由这组不等式，我们可以得到，如果序列中存在 $t_i+b_i$ 升序的地方，一定不合法。

因此可以将 $t_i+b_i$ 降序排序，如果每一组 $t_i+b_i$ 都互不相同，则正确答案只有可能是当前这组序列。

所以我们只需证明，对于一段连续相同的 $t_i+b_i$，对它们任意重新排列，都不影响其合法性。

假设存在一组 $(t_1,b_1)\cdots(t_k,b_k)$ 是合法的，且 $t_i+b_i=C$，假设 $1\le i<i+1\le k$，我们只关注 $i,i+1$ 这两个要被交换的位置，交换前：

$$\begin{aligned} T+b_1+\dots+b_{i-1}&>C-b_i\\ T+b_1+\dots+b_{i-1}+b_i&>C-b_{i+1} \end{aligned}$$

交换后：

$$\begin{aligned} T+b_1+\dots+b_{i-1}&>C-b_{i+1}\\ T+b_1+\dots+b_{i-1}+b_{i+1}&>C-b_{i} \end{aligned}$$

虽然这两个不等式组中，上面的式子不一样，下面的式子一样，但是下面的式子可以推出上面的式子（注意 $b$ 是负的）。

也就是说这两个不等式组的上面的式子都已经被下面的式子蕴含，所以我们只需要对比下面的式子。

这两个式子又是等价的，所以合法的序列一段连续相同的 $t_i+b_i$ 任意重排都是合法的。

这也解释了，为什么 $b_i\ge 0$ 时不能这么做。因为当 $b_i\ge 0$ 时下面的式子被上面的蕴涵，而这两个不等式组中上面的式子并不等价。

所以我们证明了，如果存在一个合法的序列，那么任意按照 $t_i+b_i$ 降序排序后的序列一定也合法。

我们考察对 $t_i+b_i$ 降序排序后的任意一个序列：

1. 如果它是合法的，那么就存在了一个合法序列。
2. 如果它不合法，而存在这样一个合法序列，我们一定可以将这个合法序列，通过上面证明的方式，重排成这个不合法的序列，这就矛盾了。所以不存在合法序列。

所以只需要对 $t_i+b_i$ 排序后检查即可。

Luogu P1080

首先要指出，我们在推导公式的时候不需要在意下取整这个条件，因为不取整的答案，最后给它取整，也是它问的这个答案。

设 $a_0,b_0$ 是国王，大臣是 $a_i,b_i$，根据题面 $w_i=\frac{\prod_{j=0}^{i-1} a_j}{b_i}$，我们可以对大臣任意重排，找到最小的 $\max w_i$。

如果对两个相邻的位置 $i,i+1$ 交换后，显然只会改变 $w_i,w_{i+1}$。

交换前，有 $w_1=(\prod_{j=0}^{i-1}a_j)\frac{1}{b_i},w_{2}=(\prod_{j=0}^{i-1}a_j)\frac{a_i}{b_{i+1}}$；

交换后，有 $w_1'=(\prod_{j=0}^{i-1}a_j)\frac{1}{b_{i+1}},w_2'=(\prod_{j=0}^{i-1}a_j)\frac{a_{i+1}}{b_i}$。

如果交换后更优，即 $\max\{w_1,w_2\}> \max\{w_1',w_2'\}$，会有不等式 $\max\{b_{i+1},a_ib_i\}> \max\{b_i,a_{i+1}b_{i+1}\}$。

我们观察到 $a_ib_i$ 作为一个整体出现，所以接下来我们讨论它们的大小关系。

1. $a_ib_i=a_{i+1}b_{i+1}$，此时有 $a_{i+1}b_{i+1}\ge b_i$，同理 $a_ib_i\ge b_{i+1}$，于是这两个式子相等。
2. $a_ib_i<a_{i+1}b_{i+1}$，此时有 $a_{i+1}b_{i+1}>b_i$，那么不等式转化为 $b_{i+1}>a_{i+1}b_{i+1}$ 或 $a_ib_i>a_{i+1}b_{i+1}$，它们都不成立。
3. $a_ib_i>a_{i+1}b_{i+1}$，此时有 $a_ib_i>b_{i+1}$，那么不等式转化为 $a_ib_i>b_i$ 且 $a_ib_i>a_{i+1}b_{i+1}$，容易观察到只有 $a_i=1$ 且 $a_{i+1}b_{i+1}\le b_i$ 时，这两个式子才会相等，否则是大于号。

因此，当 $a_ib_i\ge a_{i+1}b_{i+1}$ 时，交换 $i,i+1$ 不会让答案更劣，于是我们将序列按照 $a_ib_i$ 升序排序。

假设某个序列对应的答案最小，那么我们把它按照 $a_ib_i$ 升序排序，答案还是最小的。并且，对于那些 $a_ib_i$ 相等的段，任意交换不会改变答案。

因此我们把原序列按照 $a_ib_i$ 升序排序求的答案就是最小的。

Luogu P6155

如果找到了一组 $d_i=a'_i-a_i$，根据邻项交换的思路，如果交换使得答案不会更劣，那么：

$$d_ib_i+d_{i+1}b_{i+1}\ge d_ib_{i+1}+d_{i+1}b_i$$

移项可得：

$$d_i(b_i-b_{i+1})\ge d_{i+1}(b_i-b_{i+1})$$

由于 $b$ 可以任意安排顺序，如果 $b_i-b_{i+1}\ge 0$，即 $b$ 非严格递减，现在假设有了一个最佳答案对应的序列 $d$。

对于 $b_i=b_{i+1}$ 的连续段，$d$ 可以任意安排，我们现在关注 $b_i>b_{i+1}$ 的地方。

在这些位置，当 $d_{i}=d_{i+1}$ 时，任意交换不影响答案；当 $d_i>d_{i+1}$ 时，交换一定会使答案更小，与假设矛盾，所以 $d_{i}\le d_{i+1}$。

所以，按照 $d$ 升序排序的任意一个序列的答案都和最优答案相同，接下来我们看怎么安排 $d$。

我们把 $a$ 升序排序，如果 $a$ 互不相同，那么答案就是 $0$。

如果某个 $a_i$ 最终不用修改，那么它的 $d_i=0$，直觉上我们希望它尽量多，接下来证明这一点：

假设最终将 $a_j\gets a_j+d_j=a_i$，并且最终将 $a_i\gets a_i+d_i$，那么，这两个地方的贡献是 $d_jb_x+d_ib_y$；

如果直接将 $a_j\gets a_j+d_j+d_i$，这两个地方的贡献可以是 $(d_j+d_i)\min\{b_x,b_y\}\le d_jb_x+d_ib_y$。

所以我们可以让最优答案的方案，使其尽量不修改某个 $a_i$，这样最优答案仍然不变。

如果只有一段连续的 $a_i=\cdots=a_j$，显然我们让 $a_i\sim a_n$ 修改后的值连续地充满值域是最优的，注意这里说的是 $a_n$，也就是如果增加某个 $a_i\sim a_j$ 中的值，它与后面的 $a_{j+1}\sim a_n$ 值相同，那么就增加它直到不同。

显然，任何其它的安排都会让 $d_i\sim d_j$ 某个值严格增加，所以这样的方案最优。

然后，我们考虑两段连续的 $a_{l_1}\sim a_{r_1}$ 与 $a_{l_2}\sim a_{r_2}$。如果我们先安排完了 $a_{l_2}\sim a_{r_2}$，那么对于前面的 $a_{l_1}\sim a_{r_1}$，它会有两种可能性。

1. $a_{l_1}\sim a_{r_1}$ 与 $a_{l_2}\sim a_{r_2}$ 之间的 gap 足够用来填 $a_{l_1}\sim a_{r_1}$ 修改后的值。

2. 当它们之间的 gap 不足够填时，可能有两种选择：要么给某个 $a_j'$ 的位置换给 $a_i+d_i$，要么给 $a_i\gets a_i+d_i$ 大于所有的 $a_j+d_j$。

   这两种方案对应的 $d_i+d_j$ 是相同的，我们不妨设它们对应的 $b_1>b_2$，那么可以证明，当 $d_i+d_j$ 相同时，$d_{mx}$ 越大，$d_{mx}b_2+d_{mn}b_1$ 越小。这可以做差证明。

所以我们可以从后往前，尽量找一个小的没有用过的空位填上。

由于这样的空位有 $O(n)$ 个，所以我们可以用一个 umap 开并查集并且惰性维护并查集的值。$i$ 节点的父亲的意思是第一个 $\ge i$ 的空位。

Luogu P1986/P1250

对于这样一个线段覆盖的问题，我们首先会按照某个端点排序，这里不妨就按左端点排序。

这有什么用处？这能够保证，在线段 $s_i$ 之前的线段 $s_j,j<i$，都是有可能和它相交的。

回到这个问题。如果我们能填一个数，我们一定希望它尽可能出现在相交多的地方。

现在我们考虑 $s_n(l_n,r_n)$，如果把前面每一个的 $s_i(i<n)$ 和它相交的位置的权值 $+1$，那么最终从 $l_n\sim r_n$ 的权值是非严格递减的。

因此，我们从左向右一个个填，直到到满足条件。通过前面的逻辑，我们可以判断，最优解经过这样调整一定还是最优解。

ICPC 2024 Online II J

我们发现，交换相邻位置 $(i,i+1)$ 对前后的值并不会产生影响，所以我们看一下交换前后这两项的变化。

交换前，$v_i-c_iW+v_{i+1}-c_{i+1}(W+w_i)$；

交换后，$v_{i+1}-c_{i+1}W+v_i-c_i(W+w_{i+1})$。

两式做差可以得到：$-c_{i+1}w_i+c_iw_{i+1}\ge 0$，说明交换后答案不会更差。

所以把最优答案根据 $c_{i}/w_i$ 升序排序，最优解仍然最优。