蓝桥杯真题代码记录(最优清零方案

简介: 蓝桥杯真题代码记录(最优清零方案

1. 题目:


给定一个长度为 N 的数列 41,42,…,AN 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。

每次操作小蓝可以选择以下两种之一:

1.选择一个大于0的整数,将它减去1;

2.选择连续 区 个大于 0 的整数,将它们各减去1。

小蓝最少经过几次操作可以将整个数列清零?

输入格式

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

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

输出格式

输出一个整数表示答案。

样例输入

4 2

1 2 3 4

样例输出

6

2. 我的代码:

import os
import sys

# 贪心算法

N, K = map(int, input().split(" "))
l = list(map(int, input().split(" ")))

result = 0

# 指针记录第一个>0的点
n_p = 0

while n_p <= len(l) - K:
    # 遍历整个l
    while l[n_p] <= 0:  # 跟踪到第一个大于0的点
        n_p += 1
        if n_p > len(l) - K:
            break
    if n_p > len(l) - K:
        break

    # 先使用第二种减法(循环减去 K 个 1)
    new_n_p = N
    min_n = 10000000000000

    for min_p in range(n_p + K - 1, n_p - 1, -1):
        if l[min_p] < min_n:
            new_n_p = min_p
            min_n = l[min_p]

    if min_n != 0:  # 第二种减法
        for i in range(n_p, n_p + K):
            l[i] -= min_n

    result += min_n

    # 第一种减法
    result += sum(l[n_p: new_n_p + 1])
    n_p = new_n_p

result += sum(l[n_p:])

print(result)
目录
相关文章
|
1月前
|
网络安全 数据安全/隐私保护 计算机视觉
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
|
1月前
蓝桥杯真题代码记录(直线
蓝桥杯真题代码记录(直线
15 0
|
1月前
蓝桥杯真题代码记录(卡片
蓝桥杯真题代码记录(卡片
18 0
|
1月前
蓝桥杯真题代码记录(蜂巢
蓝桥杯真题代码记录(蜂巢
12 0
|
1月前
蓝桥杯真题代码记录(数位排序
蓝桥杯真题代码记录(数位排序
14 0
|
1月前
蓝桥杯真题代码记录(纸张尺寸
蓝桥杯真题代码记录(纸张尺寸
11 0
|
1月前
蓝桥杯真题代码记录(保险箱
蓝桥杯真题代码记录(保险箱
15 1
蓝桥杯真题代码记录(保险箱
|
1月前
|
传感器
蓝桥杯真题代码记录(管道
蓝桥杯真题代码记录(管道
17 2
|
1月前
|
索引
蓝桥杯真题代码记录(松散子序列
蓝桥杯真题代码记录(松散子序列
14 0
|
1月前
蓝桥杯vip测试题系统-数组求和(解题思路以及解题代码,手画思路图虽然丑丑的)
蓝桥杯vip测试题系统-数组求和(解题思路以及解题代码,手画思路图虽然丑丑的)
35 0