这把锁从左到右有 � n 个数,组成了一个序列 { � } {a}。 由于 GOD_hj 的记性不好,所以只要将锁设置为输入任意单峰序列即可打开。具体为: � 1 ≤ ⋯ ≤ � � ≥ � � + 1 ≥ ⋯ ≥ � � ( 1 ≤ � ≤ � ) a 1 ≤⋯≤a i ≥a i+1 ≥⋯≥a n (1≤i≤n) GOD_hj 的锁是拨动式的,即拨一下就能换成临近的一个数( 0 0 和 9 9 可以互换)。 求最少拨几下可以开锁。
时间: 2024-04-02 18:31:36 浏览: 14
这是一个经典的信封嵌套问题,也可以称为最长不降子序列问题。可以使用动态规划求解,时间复杂度为 O(n^2) 或 O(nlogn)。以下是 O(nlogn) 的解法:
定义一个数组 d,d[i] 表示长度为 i 的最长不降子序列的末尾元素的最小值。初始化 d[1] = a[1],其余为正无穷大。
遍历整个序列,对于每个元素 a[i],在数组 d 中二分查找第一个大于等于 a[i] 的位置,更新 d[j] = a[i],其中 j 为查找到的位置。如果查找到的位置 j 大于当前最长的不降子序列长度 len,则更新 len = j。
最终最长不降子序列的长度为 len,需要拨动的次数为 n - len。
代码如下:
相关问题
GOD_hj 有一把数字密码锁,但是他陷于 whk,没时间来开锁。这把锁从左到右有 nn 个数,组成了一个序列 \{a\}{a}。 由于 GOD_hj 的记性不好,所以只要将锁设置为输入任意单峰序列即可打开。具体为: a_1 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n\quad (1 \le i \le n) a 1 ≤⋯≤a i ≥a i+1 ≥⋯≥a n (1≤i≤n) GOD_hj 的锁是拨动
的,每次只能将一个数字上下拨动一格。现在问你:最少需要多少次拨动才能将锁打开?
注:单峰序列是指序列从左到右单调不降,从左到右单调不增的序列。
我的回答是:
先找到最大值的下标 $i$,然后分别从开头到 $i$ 和从结尾到 $i$ 找到单调不降的长度 $len1$ 和 $len2$,最终答案为 $n-\max(len1,len2)$。
时间复杂度 $O(n)$。
代码实现:
```python
n = int(input())
a = list(map(int, input().split()))
i = a.index(max(a))
len1, len2 = 1, 1
for j in range(i-1, -1, -1):
if a[j] <= a[j+1]:
len1 += 1
else:
break
for j in range(i+1, n):
if a[j] <= a[j-1]:
len2 += 1
else:
break
print(n - max(len1, len2))
```
matlab选取一时间序列从第n个开始组成新序列
假设原始时间序列为 `x`,需要从第 `n` 个开始组成新序列,可以使用如下代码:
```matlab
n = 5; % 从第5个开始
new_x = x(n:end);
```
其中,`n` 为起始位置,`end` 表示截取到原始序列的最后一个元素。执行完以上代码后,`new_x` 就是从第 `n` 个开始的新序列。