B. Shrinking Array

问题描述

一个数组 $b$ 被称为美丽的，如果：

• 它至少包含两个元素
• 存在一个位置 $i$，使得 $|b_i - b_{i+1}| \leq 1$

给定一个数组 $a$，当数组至少有两个元素时，你可以执行以下操作：

1. 选择数组 $a$ 中的两个相邻位置 $i$ 和 $i+1$
2. 选择一个整数 $x$，使得 $\min(a_i, a_{i+1}) \leq x \leq \max(a_i, a_{i+1})$
3. 从数组中移除数字 $a_i$ 和 $a_{i+1}$，并在它们的位置插入数字 $x$

每次操作后，数组的大小减少 1。

任务：计算使数组变得美丽所需的最少操作次数，或者报告这是不可能的。

题解

答案只能是 -1、0 或 1。

算法

1. 检查是否已经美丽（答案：0）

   • 如果存在两个相邻元素的绝对差 ≤ 1，答案是 0

2. 检查一次操作是否足够（答案：1）

   • 对于每对相邻元素，我们可以将它们合并得到一个介于它们之间的新元素
   • 检查这个合并位置之前或之后的元素是否会创建一个美丽的数组
   • 如果存在任何这样的对，答案是 1

3. 否则（答案：-1）

   • 如果不存在任何可以导致美丽数组的相邻元素对，答案是 -1

关键洞察

可以证明，合并超过一对相邻元素无助于得到一个美丽的数组，所以我们只需要考虑最多一次操作。

实现

查看提交