题解 CF1032C 【Playing Piano】

· · 题解

一个复杂度和 b_i 范围无关的构造方法。

首先，为了方便处理只有一个元素或最后两个元素相等的情况，在 a 的末尾添加一个值为 a_n 的元素。

把数组分成若干水平段、下降段和上升段：

  1. 水平段，b_i 可以取 2 或者 3，保证和 b_{i-1} 不同即可。
  2. 下降段，b_i 可以从 5 开始，如果 b_{i-1} 也是 5，那就从 4 开始，然后每次减少 1。
  3. 上升段，b_i 可以从 1 开始，如果 b_{i-1} 也是 1，那就从 2 开始，然后每次增加 1。

如果上述过程产生了不在 [1,5] 中的数则输出 -1。

复杂度为 O(n)。

AC 代码（Golang）：

package main
import("bufio";."fmt";"os")

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var n int
    Fscan(in, &n)
    a := make([]int, n, n+1)
    for i := range a {
        Fscan(in, &a[i])
    }
    a = append(a, a[n-1]) // 末尾加个哨兵，方便处理只有一个元素 or 最后两个元素相等的情况
    b := make([]int, n)
    for i := 0; i < n; {
        if a[i] == a[i+1] {
            if b[i] == 0 {
                b[i] = 2
                if i > 0 && b[i-1] == 2 {
                    b[i] = 3
                }
            }
            i++
            continue
        }
        st := i
        // 处理连续下降段或连续上升段
        for i += 2; i < n && a[i] != a[i-1] && a[i] < a[i-1] == (a[i-1] < a[i-2]); i++ {
        }
        if a[st] > a[st+1] {
            b[st] = 5
            if st > 0 && b[st-1] == 5 {
                b[st] = 4
            }
            for st++; st < i; st++ {
                b[st] = b[st-1] - 1
            }
        } else {
            b[st] = 1
            if st > 0 && b[st-1] == 1 {
                b[st] = 2
            }
            for st++; st < i; st++ {
                b[st] = b[st-1] + 1
            }
        }
        i--
        if b[i] < 1 || b[i] > 5 {
            Fprint(out, -1)
            return
        }
    }
    for _, v := range b {
        Fprint(out, v, " ")
    }
}