题解：P5868 [SEERC 2018] Min Max Convert
·
问题理解 Problem understanding
我们有两个长度为N的数列A和B。我们可以对数列A进行两种操作：
-
最大值操作：选择一个区间[a, b]，将该区间内的所有元素替换为该区间内的最大值。
-
最小值操作：选择一个区间[a, b]，将该区间内的所有元素替换为该区间内的最小值。
我们的目标是通过一系列操作（最多2N次）将数列A变为数列B。如果无法实现，则输出-1。
思路 mentality
1.遍历数列B，检查每个元素是否在数列A中出现过。如果某个元素在数列A中不存在，则输出-1。
2.检查数列B中的每个元素是否可以通过最大值或最小值操作从数列A中得到。
构造操作序列：
从数列B的末尾开始，逐步构造操作序列。
对于每个位置i，如果A[i] != B[i]，则选择一个操作将A[i]变为B[i]。
-
如果B[i] > A[i]，则需要使用最大值操作。
-
如果B[i] < A[i]，则需要使用最小值操作。
记录操作：
每次操作后，更新数列A的状态。
记录每次操作的类型和区间。
集算法之大成！助力oier实现梦想！
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)