问题求解II-HW07 题解
Problem A: 数字接龙
- 给定 $n$ 个数的序列，求将其首尾相接能组成的最大的数。
- $n\leq 50000$。
令 $w(x)=10^{x的位数}$。首先，在最优解中，相邻的两个数 $A,B$ 一定满足 $\overline{AB}\geq \overline{BA}$。又 $\overline{AB}\geq \overline{BA}$ 意味着 $Aw(B)+B\geq Bw(A)+A$，移项化简可得 $\frac{A}{w(A)-1}\geq \frac{B}{w(B)-1}$，所以我们只需要将所有数按照 $\frac{x}{w(x)-1}$ 的值从大到小排序再拼接即可获得最优解 (该属性值相同的若干个连续数无论如何换序不会影响答案)。
Problem B: 优化
- 给定包含 $n$ 个整数的集合 $S$，要求恰好移除 $k$ 个数，使得剩下的数中 $\min_{x,y\in S，x\neq y}x-y$ 最大。
- $1\leq k, n\leq 10^5, n-k\geq 2$。
见 这份题解 的第一题。