蓝桥杯python编程每日刷题 day 20

题目：

给定一个长度为 N 的整数序列：A1, A2, · · · , AN。现在你有一次机会，将其中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。 

最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。 

输入格式

输入第一行包含两个整数 N 和 K。

第二行包含 N 个整数 A1, A2, · · · , AN。 

输出格式

输出一行包含一个整数表示答案。
（1）代码：

 
##########################输入部分
n, k = map(int, input().split())
arr = [int(i) for i in input().split()]
 
l = n
notk_max = 0
zd = [0 for i in range(l)]
 
######################################代码部分
 
def bs(t,a,mid):
    if t:
        return mid <= a
    else:
        return mid >= a
 
 
def erf(t,dp,a):#找到新元素在单调栈中的位置,t为False是自左往右第一个小于a，t为True是自左往右第一个大于a
    if not dp:
        return -1
    l,r=0,len(dp)-1
    while l<r:
        mid=(l+r)//2
        if bs(t,a,dp[mid]):#缩头
            l=mid+1
        else:
            r=mid
    return -1 if bs(t,a,dp[l]) else l
 
def zhao2():  # 得出以我结尾的的最长子序列
    global zd, notk_max, arr, k, l
    dp = []
    for i in range(l - k):
        wz = erf(True, dp, arr[i])
        if wz < 0:
            dp.append(arr[i])
            zd[i] += len(dp)
        else:
            dp[wz] = arr[i]
            zd[i] += (wz + 1)
        if zd[i] > notk_max:
            notk_max = zd[i]
 
 
def zhao1():  # 得出以我开头的最长子序列 (不包括自己)，以及k在最左侧的not_kmax
    global zd, notk_max, arr, k, l
    dp = []
    for i in range(l - 1, k, -1):
        wz = erf(False, dp, arr[i])
        if wz < 0:
            dp.append(arr[i])
        else:
            dp[wz] = arr[i]
        #######以下为zd赋值
        wz = erf(False, dp, arr[i - k - 1])
        if wz < 0:
            zd[i - k - 1] = len(dp)
        else:
            zd[i - k - 1] = wz
    ########以下得出k覆盖最左 最长不下降子序列长度
    notk_max = len(dp)
    wz = erf(False, dp, arr[k])
    if wz < 0:
        notk_max += 1
 
 
##############################################输出部分
zhao1()
zhao2()
print(notk_max + k)

（1）解析：

1.在代码中的前两个函数为辅助判断二次搜查

def bs(t,a,mid):
    if t:
        return mid <= a
    else:
        return mid >= a
 
 
def erf(t,dp,a):#找到新元素在单调栈中的位置,t为False是自左往右第一个小于a，t为True是自左往右第一个大于a
    if not dp:
        return -1
    l,r=0,len(dp)-1
    while l<r:
        mid=(l+r)//2
        if bs(t,a,dp[mid]):#缩头
            l=mid+1
        else:
            r=mid
    return -1 if bs(t,a,dp[l]) else l
首先我们用t = True，来表示找到在dp这个列表中，比a大的数，首先用二分搜查，来确定比a大的属的序列在哪里，用辅助函数bs来判断，当t为True时，dp[mid]比a小，说明此时mid不是我们要找的序列，将l更新，直到找到我们需要的序列，最后返回l

接下来对主题函数的思想进行分析，首先将k想象为一个可以覆盖元素的滑动窗口，自左往右滑动，k每滑动一次我们就从没有被k覆盖的元素中找最长不下降子序列。而k自左往右滑动完，出现过的最长的最长不下降子序列的长度＋k就是我们要的答案

案例 ：1，4，2，8，5   。k=2     max=0

（1）k覆盖1，4。从剩余的2，8，5找得最长不下降子序列，2，8。或2，5。max=2

（2）k覆盖4，2。从剩余的1，8，5找得最长不下降子序列 1，8。1，5。max不变

（3）k覆盖2，8。从剩余的1，4，5找得最长不下降子序列1，4，5。max=3

（4）k覆盖8，5。.........max不变

最终max+k就是我们要的答案

2.zhao2的作用是将前（n-k）个数的最佳排序调整到notk——max，并解释一下global用法，用 global 之后的变量将不只局限函数，而是放大于整体程序，在函数中变量的变值可以在函数以外的程序中使用

def zhao2():  # 得出以我结尾的的最长子序列
    global zd, notk_max, arr, k, l
    dp = []
    for i in range(l - k):（此时l为n）
        wz = erf(True, dp, arr[i])
        if wz < 0:
            dp.append(arr[i])
            zd[i] += len(dp)
        else:
            dp[wz] = arr[i]
            zd[i] += (wz + 1)
        if zd[i] > notk_max:
            notk_max = zd[i]

第1步：处理 arr[0] = 3

1. ​查找插入位置：
   • erf(True, [], 3) → 空栈直接返回 -1。
2. ​更新 dp 和 zd：
   • wz = -1 → 执行 dp.append(3) → dp = [3]。
   • zd[0] = len(dp) = 1（以 3 结尾的 LNDS 长度为 1）。
3. ​更新全局最大值：
   • notk_max = max(0, 1) = 1。

​第2步：处理 arr[1] = 1

1. ​查找插入位置：
   • erf(True, [3], 1) → 找第一个 >1 的数（3 在索引 0）。
   • 返回 0。
2. ​更新 dp 和 zd：
   • wz = 0 → 替换 dp[0] = 1 → dp = [1]。
   • zd[1] = wz + 1 = 1（以 1 结尾的 LNDS 长度为 1）。
3. ​全局最大值：
   • notk_max 保持 1（未更新）。

​第3步：处理 arr[2] = 4

1. ​查找插入位置：
   • erf(True, [1], 4) → 找第一个 >4 的数（无，返回 -1）。
2. ​更新 dp 和 zd：
   • wz = -1 → dp.append(4) → dp = [1, 4]。
   • zd[2] = len(dp) = 2（以 4 结尾的 LNDS 为 [1, 4]）。
3. ​全局最大值：
   • notk_max = max(1, 2) = 2。

​第4步：处理 arr[3] = 2

1. ​查找插入位置：
   • erf(True, [1, 4], 2) → 找第一个 >2 的数（4 在索引 1）。
   • 返回 1。
2. ​更新 dp 和 zd：
   • wz = 1 → 替换 dp[1] = 2 → dp = [1, 2]。
   • zd[3] = wz + 1 = 2（以 2 结尾的 LNDS 为 [1, 2]）。
3. ​全局最大值：
   • notk_max 保持 2。

​3. 最终结果

• zd = [1, 1, 2, 2, 0]：
  • zd[0]=1：子序列 [3]
  • zd[1]=1：子序列 [1]
  • zd[2]=2：子序列 [1, 4]
  • zd[3]=2：子序列 [1, 2]
• notk_max = 2（前 n-k=4 个元素的最长 LNDS 长度）。

3.接下来为后（n-k）个元素的最佳排序，首先对

从右向左扫描，计算以每个位置开头的 LNDS 长度
 

def zhao1():  # 得出以我开头的最长子序列 (不包括自己)，以及k在最左侧的not_kmax
    global zd, notk_max, arr, k, l
    dp = []
    for i in range(l - 1, k, -1):
        wz = erf(False, dp, arr[i])
        if wz < 0:
            dp.append(arr[i])
        else:
            dp[wz] = arr[i]
        #######以下为zd赋值
        wz = erf(False, dp, arr[i - k - 1])
        if wz < 0:
            zd[i - k - 1] = len(dp)
        else:
            zd[i - k - 1] = wz
    ########以下得出k覆盖最左 最长不下降子序列长度
    notk_max = len(dp)
    wz = erf(False, dp, arr[k])
    if wz < 0:
        notk_max += 1

在wz = erf(False, dp, arr[i - k - 1])以上的代码用于更新dp之后的代码适用于将前（n-k）个数与后（n-k）连接起来

i - k - 1 的物理意义

• ​**i**：当前反向遍历的位置（从 n-1 到 k+1）。
• ​**k**：允许修改的连续元素个数。
• ​**i - k - 1：
  ​表示前 n - k 个元素中，与当前反向位置 i 对应的“连接点”​**。
  这个位置是 ​前 n - k 个元素的尾部，用于检查是否能与后 n - k 个元素的头部拼接。

​ 为什么需要 i - k - 1？

• ​动态拼接的核心：
  修改 k 个元素后，前 n - k 和后 n - k 部分的子序列需要通过某个值连接。
  i - k - 1 标记了前 n - k 部分的最后一个元素，用于判断是否能与后 n - k 部分的第一个元素形成不下降序列。

​具体例子说明

输入：arr = [3, 1, 4, 2, 8]，n=5，k=1（修改 1 个元素）。

• ​前 n - k = 4 个元素：[3, 1, 4, 2]（不修改部分）。
• ​反向遍历范围：i = 4, 3, 2（对应 arr[4]=8, arr[3]=2, arr[2]=4）。

​步骤解析：​

1. ​**i = 4（arr[4] = 8）​**：

   • i - k - 1 = 2（即 arr[2] = 4）。
   • ​作用：检查 4（前部分的最后一个值）是否能与 8（后部分的第一个值）拼接。
     • 若 4 <= 8，则可以连接，此时 zd[2] 记录反向 LNDS 长度。
     • 本例中 4 <= 8，zd[2] 被更新为反向长度 1（[8]）。

2. ​**i = 3（arr[3] = 2）​**：

   • i - k - 1 = 1（即 arr[1] = 1）。
   • ​作用：检查 1 是否能与 2 拼接。
     • 1 <= 2，可以连接，zd[1] 更新为反向长度 2（[2, 8]）。

3. ​**i = 2（arr[2] = 4）​**：

   • i - k - 1 = 0（即 arr[0] = 3）。
   • ​作用：检查 3 是否能与 4 拼接。
     • 3 <= 4，可以连接，zd[0] 更新为反向长度 2（[4, 8]）。

​关键作用总结

​ 为什么这样设计？

• ​高效性：避免显式枚举所有可能的修改方案，通过反向扫描直接计算可能的最优连接点。
• ​正确性：确保前 n - k 和后 n - k 部分的子序列能通过某个值（可能是修改后的 k 个元素）无缝拼接。

​ 最终结果的意义

• ​**zd 数组**：
  • zd[i] 表示以 arr[i] 开头或结尾的 LNDS 长度。
  • 例如 zd = [2, 2, 1, 2, 0] 表示：
    • 从 3 开头的 LNDS 长度为 2（[3, 4]）。
    • 从 1 开头的 LNDS 长度为 2（[1, 2]）。
• ​**notk_max + k**：
  结合正向和反向结果，允许修改 k 个元素时的最长 LNDS（如 [1, 4, 8] 长度为 3）。

​总结

i - k - 1 是算法中 ​连接前后子序列的桥梁，通过反向扫描动态更新 zd 数组，确保能高效计算出修改 k 个元素后的最优解。其核心思想是：
​“前 n - k 的末尾必须 ≤ 后 n - k 的开头”​，而 i - k - 1 正是找到这个关键连接点的索引。

4.接下来解释如何取得最大的值

首先我们已经取得了前（n-k）个数和后（n-k）个数的最佳排序，用notk_max代替两个值相加，再用其加上k即可
notk_max = len(dp)
    wz = erf(False, dp, arr[k])
    if wz < 0:
        notk_max += 1

数字示例

​输入：

• arr = [3, 1, 4, 2, 8]，n=5，k=1（修改 1 个元素）。
• ​前 n-k=4 个元素：[3, 1, 4, 2]。
• ​后 n-k=4 个元素：[1, 4, 2, 8]（反向扫描从 i=4 到 i=1）。

​步骤解析：

​**(1) zhao2() 正向扫描后：​**

• zd = [1, 1, 2, 2, 0]（前 n-k 部分的 LNDS 长度）：
  • zd[0]=1：[3]
  • zd[1]=1：[1]
  • zd[2]=2：[1,4]
  • zd[3]=2：[1,2]

​**(2) zhao1() 反向扫描时：​**

• ​初始化：dp = []（反向单调栈），notk_max = 0。
• ​处理 i=4（arr[4]=8）​：
  • dp = [8]（反向 LNDS 长度 len(dp)=1）。
  • i-k-1=2（arr[2]=4）：
    • 检查 4 <= 8（可以拼接）。
    • notk_max = max(0, zd[2] + len(dp)) = max(0, 2+1) = 3。
• ​处理 i=3（arr[3]=2）​：
  • dp = [8, 2]（反向 LNDS 长度 len(dp)=2）。
  • i-k-1=1（arr[1]=1）：
    • 检查 1 <= 2（可以拼接）。
    • notk_max = max(3, zd[1] + len(dp)) = max(3, 1+2) = 3（未更新）。
• ​处理 i=2（arr[2]=4）​：
  • dp = [8, 4]（替换 2 为 4，保持递减）。
  • i-k-1=0（arr[0]=3）：
    • 检查 3 <= 4（可以拼接）。
    • notk_max = max(3, zd[0] + len(dp)) = max(3, 1+2) = 3（未更新）。
• ​最终 notk_max = 3：
  • 对应子序列 [1,4,8]（前 [1] + 后 [4,8]，修改 arr[0]=1）。

​**(3) 输出 notk_max + k = 3 + 1 = 4**：

• 实际最长 LNDS 为 [1,1,4,8]（修改 arr[0]=1，长度 4）。

​关键点总结

​为什么这样能覆盖所有情况？

• ​不修改 k 的情况：
  notk_max 已经记录了前/后部分的最长拼接（如 [1,4,8] 长度 3）。
• ​修改 k 的情况：
  通过 + k 直接扩展长度（如修改 arr[0]=1，得到 [1,1,4,8] 长度 4）。
• ​数学保证：
  最长 LNDS 必然由以下两种之一构成：
  1. 不修改 k 时的 notk_max。
  2. 修改 k 时的 notk_max + k（因为修改的 k 个元素可以完美连接前后部分）。