2019网易秋招笔试编程题：瞌睡

本是古典何须时尚 2022-05-16 04:16 215阅读 0赞

题目链接：[https://www.nowcoder.com/questionTerminal/93f2c11daeaf45959bb47e7894047085][https_www.nowcoder.com_questionTerminal_93f2c11daeaf45959bb47e7894047085]  
来源：牛客网

--------------------

# 题目 #

小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。

#### 输入描述 ####

第一行 n, k (1 <= n, k <= 105) ，表示这堂课持续多少分钟，以及叫醒小易一次使他能够保持清醒的时间。  
第二行 n 个数，a1, a2, … , an(1 <= ai <= 104) 表示小易对每分钟知识点的感兴趣评分。  
第三行 n 个数，t1, t2, … , tn 表示每分钟小易是否清醒, 1表示清醒。

#### 输出描述 ####

小易这堂课听到的知识点的最大兴趣值。

--------------------

#### 示例 ####

**输入**

6 3
    1 3 5 2 5 4
    1 1 0 1 0 0

**输出**

--------------------

# 思路和代码 #

"""
    思路：从左到右遍历，比较k长度内睡着0状态对应兴趣值的和，即叫醒一下提升的兴趣值。
        总值分为两部分：醒着的固定值 + 睡着的提升值的最大值
    """
    n,k =list(map(int, input().split()))
    values =list(map(int, input().split()))
    awakes =list(map(int, input().split()))
    #n,k = [6,3]
    #values = [1, 3, 5, 2, 5, 4]
    #awakes = [1, 1, 0, 1, 0, 0]
    
    base_score =0
    for i in range(n):
        if awakes[i]:
            base_score += values[i]
            values[i] =0
    
    max_boost_score =0
    for i in range(n):
        if not awakes[i]:
            boost_score =sum(values[i:min(i+k,n)])
            max_boost_score =max(boost_score,max_boost_score)
            # 加了下面的break语句，才使这个代码时间上终于达标
            # 扫描到距结尾不足k距离范围内的第一个睡着状态即可，后面的肯定不如这个的提升值大，没必要再跑，可提前结束
            ifi > n-k+1:
                break
    
    score =base_score +max_boost_score
    print(score)

运行时间：1484 ms  
占用内存：15116K  
牛客网

--------------------

[https_www.nowcoder.com_questionTerminal_93f2c11daeaf45959bb47e7894047085]: https://www.nowcoder.com/questionTerminal/93f2c11daeaf45959bb47e7894047085