排序不等式

题目描述

有一组无序序列， $a_1,a_2,\cdots,a_n$ ，你现在可以多次的交换任意一对 $(a_i,a_j)$ ,也就可以对序列重新进行排序，形成新的序列 $b_1,b_2,\cdots,b_n$ ,设 $preSum(k)=\sum_{i=1}^k b_i$ ,也就是 $b_i$ 的前缀和,现在求使 $\sum_{i=1}^npreSum(i)$ 最小的序列,也就是使前缀和的前缀和最小的 $b$ 序列

样例输入

样例输出

数据范围

$n \leqslant 10^6$

解法0: 暴力枚举

直接全排列枚举,找到最小的那个序列,

时间为 $n!\cdot n$ ,最后乘 $n$ ,因为每一次排列后求序列和是 $O(n)$ 的

代码如下

你可能会说:会超时,这个算法没用.

但是!,你运行上面的代码,观察输出数据,你一定能发现规律?

这个题目出现在这里,所以这个题目是解的(非NPC问题),所以必然存在一个方法,设为 $\Psi$ ,可以解这个问题
$\Psi$ 这个解法的时间复杂度是多少呢?显然根据 $n \leqslant 10^6$ ,要么是 $O(n)$ ,要么是 $O(nlog_2^n)$
- 根据做题目的经验,如果是 $O(n)$ 的,就是扫一遍,就出来了
- 如果是 $n\cdot log_2^n$ ,那么你学过哪些 $log_2^n$ 或 $nlog_2^n$ 的算法?

总结,我们做题目一定有规律,只是大部分时候,这些规律是无法用肉眼观察到.

但是可以用题目的数据范围来推测出解的时间复杂度,然后根据复杂度,来猜,是一个什么样的规律,或使用的是什么算法,当然这需要做题目经验

$O(1)$ ,存在数据公式
$log_2^n$ ,和有序相关的算法或数据结构
$n^2$ ,二重循环
$n<10$
- 搜索
- 状态压缩

解法1

使用特例法,方法 $\Psi$ 显然可以解下面的这些特殊的例子

0 0 0 0 0,全是 $0$
x x x x x,全是同一个数 $x$
x x x x x very-big-number,有一个超大的数,其它数都一样
x x x x x big-number very-big-number,有两大数,其中一个非常大,其它数都一样

解说…TODO

对于情况 $1,2$ ,显然无论怎么交换,得到的结果都一样.所以不需要任何操作

对于情况 $3$ ,直觉的想法就是把very-big-number放最后面,

对于情况 $4$ …

有一个直觉的想法,大的数应该放后面,因为后面的加的次数少

公式验证如下

\begin{array}{c|c|c|c|c} preSum(1) & preSum(2) & preSum(3)& \cdots & preSum(n) \\ \hline \\ b_1 & b_1 & b_1 & & b_1 \\ & + & + & & + \\ & b_2 & b_2 & & b_2 \\ & & + & & + \\ & & b_3 & & b_3 \\ & & & & + \\ & & & &\cdots \\ & & & & + \\ & & & & b_n \end{array}

得到公式

Sum(b) = n \cdot b_1+ (n-1) \cdot b_2+ \cdots + b_n

总结: 解法的核心思想:特例法,一步一步使例子变的混乱,只要数据够特别,题目就会变得简单,接题目的要求.

解法2

序列 $B$ 如下

b_1,b_2,\cdots,b_i,b_{i+1},\cdots,b_n

设此时序列 $B$ 得到的结果为

S_1= preSum(1) + preSum(2) + \cdots + preSum(n)

此时交换 $b_i,b_{i+1}$ 得到序列 $C$ 如下,和设为 $S_2$

b_1,b_2,\cdots,b_{i+1},b_{i},\cdots,b_n

发现此时只有 $preSum(i),preSum(i+1)$ 的值改变,其它的 $preSum$ 没有改变,

其时上面那句话有误,应该只有 $preSum(i)$ 产生了变化

显然

\begin{aligned} S_2 - S_1 &= preSum_B(i)+preSum_B(i+1) - preSum_C(i) - preSum_C(i+1) \\ &= (preSum_B(i)- preSum_C(i) )+(preSum_B(i+1) - preSum_C(i+1) )\\ &= (b_i-b_{i+1}) + 0 \\ &= b_i - b_{i+1} \end{aligned}

显然

若 $b_i = b_{i+1}$ ,则 $B$ 和 $C$ 一样大
若 $b_i < b_{i+1}$ ,则 $B$ 比 $C$ 小
若 $b_i > b_{i+1}$ ,则 $B$ 比 $C$ 大

综上,若一个序列 $B$ 交换相邻的两个值 $b_i,b_{i+1},b_i > b_{i+1}$ ,也就是把大的数放后面,小的放前面,可以得到一个具有更小和的序列 $C$ ,同样,容易想到, $C$ 也可以用这种方法,得到更小的序列.那么这样一直迭代下去

我们证明的这个东西,在数学上叫做排序不等于式 TODO 上标

简写如下

对于任何一个序列,都有

\text{正序和} \leqslant \text{乱序和} \leqslant \text{逆序和}

解法

f(A) = \sum_{i=1}^n a_i + f(A-\{a_n\})

可以想到 $\sum_{i=1}^n a_i$ 是定值,所以要找出最小的 $f(A-\{a_n\})$ 值

问题就变成了去除哪个元素后子集合 $B=A-\{a_i\},B \subset A$ 的值最小?

设如果 $(a_i,a_j)$ ,其中 $a_i \notin B, a_j \in B$ ,也就 $a_i$ 是去除的元素, $a_j$ 是没有去除的元素,可以想到,分情况讨论

产生了两个子集

$B_1 = A- \{a_i\}$ ,也就是 $B_1$ 不包含 $a_i$
$B_2 = A- \{a_j\}$ ,也就是 $B_2$ 不包含 $a_j$

$a_i = a_j$ ,此时, $f(B_1) = f(B_2)$
$a_i < a_j$ ,此时, $f(B_1) = f(B_2)$

如果存一处排列在 $B_1$ ,得到 $f(B_1)$ ,那只要把序列中 $a_j$ 替换成 $a_i$ ,就得到了一个新的序列,由集合 $B_2$ 中元素组合,且一定 $f(B_2) < f(B_1)$

由此,只要存一对数 $(a_i,a_j),a_i<a_j$ ,就可以得到一个更小的 $f(A-\{a_n\})$

数学描述如下

TODO 下面的这个推导好像不对,到少感觉不合适

\exists{i} \exists{j} (a_i < a_j) \to f(B_i) < f(B_j),a_i \in B_i \land a_j \in B_j \land B_i -\{a_i\} = B_j - \{a_j\}

按种逻辑推导,什么情况下可以,得到最小的 $f(A-\{a_i\})$

删除一个数,就是会得到一个集合 $B$

最后应该推导出一个结论,删除最大的那个数,应该是最小的

总结: 如果进行定位集(集合中的每个元素在最终答案里都有对应的固定位置)的集合分类?

解法

选一个数放最前面,

f(A) = n\times a_i + f(B),B = A - \{a_i\}

这个不好考虑了,

因为 $n \times a_i$ 与 $f(B)$ 都是变化量

总结