排序不等式

一句话算法

排序不等式说：两个序列同向排序时乘积和最大，反向排序时乘积和最小。

问题模型

给定一个长度为 $n$ 的序列：

现在可以任意交换元素顺序，得到一个新序列：

记：

要求让所有前缀和之和最小：

这个模型也可以理解为：一排人按某种顺序等待，每个人的耗时是 $b_i$，要让所有人的等待完成时间之和最小。

核心直觉

先把式子展开：

越靠前的数，被加的次数越多。

所以要让总和尽量小，就应该让小数承担更大的系数，让大数尽量往后放。结论是：

也就是把原序列升序排序。

算法步骤

1. 读入 $n$ 和序列 $a$。
2. 将 $a$ 升序排序。
3. 从左到右扫描：
   • prefix += a[i]；
   • answer += prefix。
4. 输出 answer。

算法证明

相邻交换证明

只需要证明：如果相邻两个数逆序，那么交换它们不会让答案变大。

设当前序列中相邻两项是：

并且 $x>y$。

交换前后，除了当前位置的前缀和会变化，后面的前缀和总和不变。因为后面看到的总和仍然是 $x+y$。

设交换前这一位的前缀和中包含的是 $x$，交换后这一位包含的是 $y$。

于是：

所以只要存在逆序相邻对，交换它们就能让答案变小。

不断交换逆序相邻对，最后一定得到升序序列。此时再也没有能让答案变小的相邻交换，因此升序序列就是最优解。

排序不等式视角

原式可以写成：

系数序列：

是降序。根据排序不等式，要让乘积和最小，另一个序列应该按相反方向排列，也就是：

这和相邻交换得到的结论一致。

复杂度分析

• 排序时间复杂度：$O(n\log n)$。
• 扫描计算答案时间复杂度：$O(n)$。
• 总时间复杂度：$O(n\log n)$。
• 额外空间复杂度：$O(1)$，不计排序函数内部栈空间和输入数组。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

        #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a.begin(), a.end());

    long long prefix = 0;
    long long answer = 0;
    for (long long x : a) {
        prefix += x;
        answer += prefix;
    }

    cout << answer << '\n';
    return 0;
}
    

测试用例

输入：

5
5 1 4 2 3

排序后为：

1 2 3 4 5

前缀和依次为：

1 3 6 10 15

输出：

35

应用分类详解

排序不等式的本质是：当每个元素被乘上不同权重时，先判断权重的大小顺序，再决定元素应该同向还是反向排列。

一、等待时间最小化

典型模式： 每个任务越早执行，影响的人越多。

识别信号： 题面出现“总等待时间”“前缀和之和”“排队”“完成时间之和”。

核心建模： 第 $i$ 个位置的耗时会被后面所有人共同承担，因此位置越靠前，权重越大。

二、带权乘积和最值

典型模式： 有两个序列，可以重新排列其中一个或两个，使 $\sum a_i b_i$ 最大或最小。

识别信号： 题面要求“重新配对”“乘积和最大/最小”“贡献为两个量相乘”。

核心建模： 两个序列同向排序得到最大乘积和，反向排序得到最小乘积和。

三、相邻交换贪心

典型模式： 题目要求安排顺序，直接看全局很难，但可以比较相邻两项交换前后的答案变化。

识别信号： “任意排列”“选择一个顺序”“相邻两项交换后只有局部贡献改变”。

核心建模： 写出交换相邻两项前后的差值，如果差值只和这两个元素有关，就能得到排序规则。

经典例题

1. luogu-P1223 排队接水是等待时间最小化的标准题。每个人的接水时间越短，就越应该排在前面。

2. 两序列乘积和最大/最小 给定两个序列，允许重新排列配对关系。若求最大值，将两个序列都升序；若求最小值，一个升序、一个降序。

3. 前缀和的前缀和最小化 正是本文模型。把目标函数展开成带权和后，可以直接看出前面的权重更大。

参考

• Rearrangement inequality
• 排序不等式