邻项交换法

问题背景：给定 $n$ 个元素 $a_1,a_2,\ldots,a_n$ ，要求求出一个最优的排列顺序 $p$ ，使得 $f(a_{p_1},a_{p_2},\ldots,a_{p_n})$ 最优。

定义一种二元关系 $\preceq$ ： $x\preceq y$ $\iff$ 对于任意的元素前缀和后缀， $f(\ldots, x,y, \ldots)$ 都不比 $f(\ldots y,x \ldots)$ 劣。

若这种关系是一种全预序（满足自反性，传递性，连接性）：

自反性： $x\preceq x$ ，根据定义显然永远成立。
传递性： $\forall a, b, c$ ，若 $a \preceq b$ 且 $b \preceq c$ ，则 $a \preceq c$ ，需要根据序关系具体验证。
连接性： $\forall a, b$ ，要么 $a \preceq b$ ，要么 $b \preceq a$ ，需要任意元素都可比。

定义 $x\sim y$ 表示 $x\preceq y$ 且 $y\preceq x$ （可以发现 $\sim$ 构成等价关系），记号 $x\prec y$ 表示 $x\preceq y$ 且 $y\preceq x$ 不成立（可以发现 $\prec$ 构成严格弱序）。

结论：则 $p$ 是最优解 $\iff$ $a_{p_1}\preceq a_{p_2} \preceq\ldots\preceq a_{p_n}$ 。若多个元素之间大小相等，即 $a_{i_1} \sim a_{i_2} \sim \ldots \sim a_{i_k}$ ，它们之间随便排列不会影响答案的最优性。

证明：

（ $\Leftarrow$ ）设 $p^*$ 为按 $\preceq$ 排序的有序排列。对于任意其他的排列 $p$ ，既然 $\preceq$ 满足全预序性质，我们总可以通过有限次交换相邻的逆序元素（即 $x$ 在 $y$ 前且 $y \prec x$ 的情况），将 $p$ 调整为 $p^*$ 。根据 $\preceq$ 的定义，每一次这样的交换都会使 $f$ 变优或保持不变。因此 $f(p^*) \ge f(p)$ 。由于 $p$ 是任意的，故 $p^*$ 是全局最优解。
（ $\Rightarrow$ ）用反证法，若存在 $p_i,p_{i+1}$ 使得 $a_{p_i}\not \preceq a_{p_{i+1}}$ ，根据连接性可知 $a_{p_{i+1}} \preceq a_{p_i}$ ，而交换之后的解一定会更优（因为 $a_{p_i} \preceq a_{p_{i+1}}$ 不成立），所以 $p$ 不是最优解，矛盾。

提示：虽然我们定义的是全预序，但调用 std::sort 的时候需要用它导出的一个严格弱序 $\prec$ 。

例题

P1012 [NOIP 1998 提高组] 拼数

题意

设有 $n$ 个正整数 $a_1 \dots a_n$ ，求一个排列 $p$ ，使得 $\operatorname{concat}(a_{p_1},a_{p_2},\ldots,a_{p_n})$ 最大。其中 $\operatorname{concat}$ 表示将若干个正整数用十进制表示写出（无前导零），按顺序拼接在一起后，以十进制解读得到的整数。

$n\le 20, a_i \le 10^9$ 。

做法

这里对于相邻的元素只需要考虑局部的性质即可，因为前缀后缀怎么取并不会影响大小比较。

定义 $\succeq$ ： $x\succ y \iff \operatorname{concat}(x,y) \ge \operatorname{concat}(y,x)$ ，然后排序即可。

具体来说 $\operatorname{concat}(x,y) \ge\operatorname{concat}(y,x)$ 恰好是把 $x,y$ 看成字符串后 $x+y\ge y+x$ （其中 $+$ 表示字符串拼接， $\ge$ 表示按字典序比较），因为这两个数的长度相同。

这种关系显然具有连接性，我们验证它确实满足传递性。若 $a+b\ge b+a$ ，可知 $a \times (10^{len(b)} - 1) \ge b \times (10^{len(a)} - 1)$ ，则 $\dfrac{a}{10^{len(a)} - 1} \ge \dfrac{b}{10^{len(b)} - 1}$ ，那么定义 $S(x) = \frac{x}{10^{len(x)} - 1}$ ，无非就是比较 $S(x)$ 的大小，而实数的比较是具有传递性的。

#include <bits/stdc++.h>
using namespace std;

bool cmp(string a, string b) {
    return a + b > b + a;
}

int main() {
    vector<string> v;
    string s;
    int n;
    cin >> n;
    int i;
    for (i = 0; i < n; i++) {
        cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end(), cmp);
    for (i = 0; i < n; i++) {
        cout << v[i];
    }
    return 0;
}

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

题意

给定 $a,b$ 和 $n$ 个二元组 $(x_i,y_i)$ ，对于排列 $p$ ，定义

$f(p) = \max_{i=1}^n \left\lfloor \dfrac{a\prod_{j=1}^{i-1}x_i}{y_i} \right\rfloor$

求 $f(p)$ 最大值。

$n\le 1000, 0 < a,b,x_i,y_i < 10000$ 。

做法

仍然考虑邻项交换，假设现在的数是 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，之前所有数的乘积是 $p$ 。

那么第一种方案（1，2）的贡献是：

$\max\left\{\left\lfloor \dfrac{p}{y_1}\right\rfloor,\left\lfloor \dfrac{px_1}{y_2}\right\rfloor\right\}$

第二种方案（2，1）的贡献是：

$\max\left\{\left\lfloor \dfrac{p}{y_2}\right\rfloor,\left\lfloor \dfrac{px_2}{y_2}\right\rfloor\right\}$

由于 $x1,x2\ge 1$ ，所以两个方案都会产生至少 $\left\lfloor \dfrac{p}{y_{1/2}}\right\rfloor$ 的贡献，只需要比较 $\left\lfloor \dfrac{px_1}{y_2}\right\rfloor$ 和 $\left\lfloor \dfrac{px_2}{y_2}\right\rfloor$ 的大小。

知道向下取整是保序的，所以先不管取整。我们可以得到，若 $x_1y_1\le x_2y_2$ ，则 $\dfrac{px_1}{y_2}\le \dfrac{px_2}{y_2}$ ，也有 $\left\lfloor \dfrac{px_1}{y_2}\right\rfloor \le \left\lfloor \dfrac{px_2}{y_2}\right\rfloor$ ，所以得证。

这个序关系的传递性是显然的。

n = int(input())
a,b = list(map(int, input().split()))
p = []
for _ in range(n):
    x,y = list(map(int, input().split()))
    p.append((x,y))

p.sort(key=lambda t:t[0]*t[1])

ans = 0
mul = a
for x,y in p:
    ans = max(ans, mul//y)
    mul *= x

print(ans)

AGC023F - 01 on Tree

题意

给定一颗 $n$ 个点的有根树，每个点有权值 $0/1$ ，求出其的一个拓扑序（要求父亲在儿子之前出现），使得逆序数最少，求出这个逆序数。

$n\le 2\times 10^5$ 。

做法

先考虑这样一个问题，有若干个 $01$ 串，现在可以将它们随便排序，怎么排序能让最后的串逆序对数量最少。

考虑邻项交换，假设两个串里面的 $01$ 数量分别是 $(c0_x, c1_x)$ , $(c0_y,c1_y)$ ，第一种方案的代价是 $c1_x \cdot c0_y$ ，第二种方案的代价是 $c1_y \cdot c0_x$ ，因此 $x$ 在 $y$ 前面的条件就是 $\dfrac{c0_x}{c1_x} \ge \dfrac{c0_y}{c1_y}$ ，按这个排序就能得到最优解。

然后对于这个问题来说，我们同样维护每个非根节点的 $0/1$ 个数。对于 $\dfrac{c0_x}{c1_x}$ 最大的那个节点，一定是在选完根之后就立刻被选择的，所以我们可以直接把它们两个合并（儿子合并， $0/1$ 个数相加），视作一个节点。然后不断进行这个过程，用一个并查集和优先队列维护即可。

复杂度 $O(n\log n)$ 。

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5+5;
vector<int> G[N];

struct Node{
    int c0, c1;
    int id;
};

struct Comp{
    bool operator()(const Node& lhs,const Node& rhs){
        // lhs.c0 / lhs.c1 < rhs.c0 / rhs.c1
        return 1ll * lhs.c0 * rhs.c1 < 1ll * rhs.c0 * lhs.c1;
    }
};

priority_queue<Node, vector<Node>, Comp> pq;

int c0[N], c1[N];
int fa[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

int treef[N];


int main(){
    int n;  cin>>n;
    fa[1] = 1;
    for(int i=2;i<=n;i++){
        int f; cin>>f;
        G[i].push_back(f);
        G[f].push_back(i);
        treef[i] = f;
        fa[i] = i;
    }

    for(int i=1;i<=n;i++){
        int x; cin>>x;
        if(x==0)c0[i]=1;
        else c1[i]=1;
    
        if(i!=1)pq.push(Node{c0[i], c1[i], i});
    }
    long long ans = 0;

    while(pq.size()){
        auto [x0,x1,u] = pq.top(); pq.pop();
        u = find(u);
        if(x0 != c0[u] || x1 != c1[u])continue;
        int f = find(treef[u]);
        fa[u] = f;
        ans += 1ll * c1[f] * c0[u];
        c1[f] += c1[u];
        c0[f] += c0[u];
        c1[u] = c0[u] = 0;

        if(f!= 1)pq.push({c0[f], c1[f], f});
    }

    cout << ans << '\n';


    return 0;
}