@[Microchip2333](/user/546145) 一种想法：
1.任意交换一组1与2的位置只会使逆序对数量变小
2.若将其中的某个1增大则1的数量减少（或2的数量减少），同时逆序对减少
by CangerYumo @ 2024-04-20 22:36:26
考虑反证法。
___
若该数列中存在比 $2$ 大的元素，找到符合该条件最末尾的元素，设为 $a_x$，若他的后面有 $k$ 个 $2$。
$$
\cdots\ a_x\ 1\ 2\ 1\ 2\ \cdots
$$
根据题意，可以令 $a_x'=a_x-1$，然后在数列的最后加上元素 $1$。
$$
\cdots\ (a_x-1)\ 1\ 2\ 1\ 2\ \cdots\ 1
$$
此时 $a_x'$ 后面的 $k$ 个 $2$ 会与新添加的 $1$ 形成 $k$ 个逆序对。由于 $a_x>2$，即 $a_x'\geq2$，故最多失去 $k$ 个逆序对，且 $a_x'$ 与新添加的 $1$ 也形成逆序对，所以新形成的逆序对多于原本的逆序对，不符合 $a$ 中逆序对数目最大。所以数列均由 $1$ 和 $2$ 组成。
___
若存在 $2$ 在 $1$ 之后，令在 $1$ 之后最靠前的 $2$ 与它前边的 $1$ 交换位置，会形成一个新的逆序对，不符合 $a$ 中逆序对数目最大。所以所有的 $2$ 都在 $1$ 之前。
by YangJZHello @ 2024-04-21 00:11:26