5920. F. 最少极值
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 We say that a local maximum of a series of numbers is a number in the series such that the previous and next numbers in the series are both strictly smaller than it. Similarly, a local minimum is a number such that the previous and next numbers are both strictly greater than it. A local extremum of a series is either a local maximum or minimum. Note that the first and last elements of a series cannot be local extrema. You've been given a partial series of numbers with some numbers in the series missing. You know that the missing numbers are all from the set of available numbers (each one may be used at most once). Your task is to fill in the missing numbers of the series such that the number of local extrema is as small as possible. If there are many such series that satisfy this contraint, you should return the one with the smallest first entry. If there is still more than one solution, you should return the one with the smallest second entry, and so on if there are still several solutions. The input will be described by a int[] series. Each element of series will be either -1, representing a missing number, or non-negative otherwise. 我们称一个数字序列中的**局部最大值**，是指序列中这样一个数字：它前面的数字和后面的数字都严格小于它。同理，**局部最小值**是指这样一个数字：它前面的数字和后面的数字都严格大于它。序列的**局部极值**指的是局部最大值或局部最小值。需注意，序列的第一个元素和最后一个元素不能是局部极值。 现在给你一个**部分数字序列**，其中有些数字是缺失的。你已知所有缺失数字均来自某一可用数字集合（每个可用数字最多使用一次）。你的任务是填补序列中的缺失数字，使得最终序列的**局部极值数量尽可能少**。 若存在多个序列都满足“局部极值数量最少”这一条件，你应返回**第一个元素最小**的序列。若仍存在多个解，则返回**第二个元素最小**的序列，以此类推（若后续元素仍有差异，继续按此规则选择）。 输入将以一个整数数组 `series` 表示。该数组的每个元素要么是 `-1`（表示缺失数字），要么是非负整数（表示已知数字）。 ## 输入格式 Length of series int[] series Length of available int[] available ## 输出格式 int[] ### 样例 ## 输入 ```in1 5 -1 -1 -1 -1 -1 5 1 2 3 4 5 ``` ## 输出 ```out1 1 2 3 4 5 ``` ## 说明 We just fill in the numbers in increasing order to avoid any local extrema. ```in2 5 1 2 -1 4 5 1 10 ``` ```out2 1 2 10 4 5 ``` ## 说明 Since we only have one choice, 10 must be a local maximum while 4 is a local minimum. ```in3 10 1 -1 6 2 4 -1 2 7 -1 -1 6 1 2 4 7 8 8 ``` ```out3 1 1 6 2 4 2 2 7 7 4 ``` ```in4 7 8 -1 6 4 -1 -1 6 3 2 3 6 ``` ```out4 8 6 6 4 2 3 6 ``` ```in5 3 -1 5 -1 3 1 1 9 ``` ```out5 1 5 9 ``` ## 数据范围 - series will contain between 1 and 50 elements, inclusive. - available will contain between 0 and 15 elements, inclusive. - Each element of series will be between -1 and 10, inclusive. - Each element of available will be between 0 and 10, inclusive. - There will be at least as many available numbers as missing ones. ## 提示 - Each available number may be used at most one time.