随笔题解 Pb. 3
来源：ABC268 F Best Concatenation
给定 $N$ 个只包含 $\texttt 1$ 到 $\texttt 9$ 的数字和字符 $\texttt X$ 的非空字符串 $S_1,S_2,\dots,S_N$。您需要将这 $N$ 个字符串拼接成一个大串 $T$，即确定一个长度为 $N$ 的排列 $P$ 然后令
在这之后，对于每一个满足 $1\leqslant i\lt j\leqslant|T|$ 的 $(i,j)$，如果 $T_i=\texttt X$ 且 $T_j$ 是数字，那么您获得与 $T_j$ 的数值相等的分数。试求您能够获得的最终分数的最大值。
$2\leqslant N\leqslant 2\times 10^5$，$\sum|S_i|\leqslant 2\times 10^5$。
$\texttt{2s/1024MB}$。
也不知道我这个题意说的清不清楚。
总之就是如果前面有一个 ‘X’ 后面有一个数字那么就获得那个数字那么多的分数。然后求最大分数。
对于每个 $S_i$，令 $A_i$ 表示其中 $\texttt X$ 的数量，$B_i$ 表示其中数字的值的总和。
考虑已经确定了排列 $P$。此时若交换 $P_i$ 和 $P_{i+1}$，不难发现分数变化量为
如果 $P$ 是最优解，上面这个变化量需要 $\leqslant 0$。整理一下得到
即 $\frac{A_{P_i}}{B_{P_i}}$ 单调不增。
那么把所有 $\frac{A_i}{B_i}$ 算出来排个序即可。注意特殊处理一下 $B_i=0$ 的情况。