A - Inversion
2huk
·
·
题解
A - Inversion
Description
给定一个长度为 n - 1 的字符串 s，由字符 \texttt < 和 \texttt > 组成。
请你构造一个长度为 n 的序列 \{x_n\}，满足以下条件，并使得其逆序对数量最少。
- 对于每个 1 \le i < n，如果 s_i = \texttt <，则 x_i < x_{i + 1}；否则如果 s_i = \texttt >，则 x_i > x_{i + 1}。
求最小的逆序对数量。
## Solution
考虑贪心的将所有的数字求出。
首先可以发现，题目中给的要求都是对于两个**相邻**的元素而言的，那么我们应该在满足当前的条件下让后面的答案最优。具体而言，对于这样一个例子：
$$
s = \{\texttt{<>><<<<<<}\cdots\}
$$
对于 $x_2$ 而言，它需要比 $x_1$ 和 $x_3$ 都大。这时可以发现 $x_1$ 的与 $x_3$ 之间的关系并不明确。而我们希望让答案的逆序对数量最小，也就是希望尽量 $x_1 < x_3$。可以发现这件事请是可以完成的，我们只需要令 $\left\{\begin{matrix}x_1= 1 \\x_2= 3 \\x_3= 2\end{matrix}\right.$ 即可。
这时发现，对于第 $4$ 个及往后的要求，答案中必定会产生逆序对而使答案变劣。那么我们考虑这样做：既然已经有 $x_2 > x_3$ 这个事实了，也就是说这里必定会产生一个逆序对，那么我们不妨让 $x_3$ 变得大一些，将损失降到最小，然后对于后面的计算就可以避免产生**可以被避免**的逆序对了。可以发现最大的可以满足条件的 $x_3$ 为 $x_2 - 1$。
同理，既然已经有了 $x_1 < x_2$ 这个事实，也就是这个条件对答案十分有利，那么我们就让它**造福后世**，即 $x_2$ 变得大一些，这样对于后面的计算也可以避免产生**可以被避免**的逆序对了。不妨令 $x_2 = x_1 + N$，这里的 $N$ 为一个较大值，不妨为 $10^9$。
也就是说我们可以这样做：
$$
x = \{1, 100, 99, 98, 200, 199, 198, 197, \cdots\}
$$
可以由上述得到这样一个贪心策略：
- 若 $s_i = \texttt <$，则 $x_i = x_{i - 1} + N$。
- 若 $s_i = \texttt >$，则 $x_i = x_{i - 1} - 1$。
可以证明，也可以凭直觉，这样构造出的 $x$ 一定是逆序对最少的。最后再求出 $x$ 中的逆序对数量即可。
## Code
求逆序对我用的 `map` 维护的树状数组：<https://atcoder.jp/contests/arc168/submissions/47767743>。