首页 > 试题广场 >

瞌睡

[编程题]瞌睡

热度指数：34288 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行 n (1 <= n <= 10⁵), k (0 <= k <= 10⁵) ，表示这堂课持续多少分钟，以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数，a₁, a₂, ... , a_n(1 <= a_i<= 10⁴) 表示小易对每分钟知识点的感兴趣评分。
第三行 n 个数，t₁, t₂, ... , t_n 表示每分钟小易是否清醒, 1表示清醒。

输出描述:

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

示例1

输入

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

输出

算法知识视频讲解

Python

君与小生丨🍃

def getMaxInterest(i,w,count):
    if len(i) == 0:
        return 0
    m = []
    maxNum = 0
    countNum = 0
    for k in range(count):
        if w[k] == 0:
            countNum += i[k]
    m.append(countNum)
    for k in range(len(w)):
        if k + count >= len(w):
            break
        if w[k] == 0:
            countNum -= i[k]
        if w[k + count] == 0:
            countNum += i[k + count]
        m.append(countNum)
    for y in range(len(w)):
        if w[y] == 1:
            maxNum += i[y]
    return max(m) + maxNum
if __name__ == '__main__':    
    a,b = map(int,input().split())
    i = list(map(int,input().split()))   
    w = list(map(int,input().split()))   
    num = getMaxInterest(i,w,b)
    print(num)

发表于 2019-09-14 23:25:29 回复(0)

Python

贾志统

n, k = map(int, input().split())
interest_list = list(map(int, input().split()))
clear_list = list(map(int, input().split()))
interest_point = 0
gets = []
for i in range(n):
    if clear_list[i] == 1:
        interest_point += interest_list[i]
        gets.append(0)
    else:
        gets.append(interest_list[i])

get = sum(gets[:k])
max_get = get
for i in range(k, n):
    get += gets[i] - gets[i-k]
    if get > max_get:
        max_get = get
print(interest_point + max_get)

发表于 2019-08-23 22:54:52 回复(0)

Python

offer快来运气up

nk = input().split()
n, k = int(nk[0]), int(nk[1])

a = [int(i) for i in input().split()]  # 评分
t = [int(i) for i in input().split()]  # 是否清醒

def getVal(i, res, flag):
    if i > n-1:
        return 0
    if t[i] == 1 and (flag == k or flag <= 0):
        res = res + a[i] + getVal(i+1, res, flag)
    else:
        if flag == k:     # 可选择是否被叫醒
            res = res + max(getVal(i+1, res, flag-1)+a[i], getVal(i+1, res, flag))
        elif 0 < flag < k:  # 说明被叫醒，一直保持加分
            res = res + a[i] + getVal(i+1, res, flag-1)
        else:  # 说明叫醒次数用完
            res = res + getVal(i+1, res, flag)
    return res

print(getVal(0, 0, k))

# 请检查是否存在语法错误或者数组越界非法访问等情况 # case通过率为40.00%

想求大佬举出反例，说明代码哪里出错了，求指导

编辑于 2019-07-17 23:12:12 回复(0)

Python

ElonB

"""
base_score 为清醒时对兴趣度a的求和
max_score 为叫醒一次，k时间内最大的兴趣度
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n, k = list(map(int, input().strip().split()))
    a = list(map(int, input().strip().split()))
    t = list(map(int, input().strip().split()))
    base_score = 0
    for i in range(n):
        if t[i]:
            base_score += a[i]
            a[i] = 0
    max_score = tmp = sum(a[:k])
    for i in range(k, n):
        tmp = tmp + a[i] - a[i - k]
        max_score = max(max_score, tmp)
    ans = base_score + max_score
    print(ans)

发表于 2019-07-03 11:36:50 回复(0)

Python

逾清风

n, k = map(int, raw_input().split(' '))
score = map(int, raw_input().split(' '))
flag = map(int, raw_input().split(' '))
if n <= k:
print sum(score)
else:
flag_sum = 0
for i in range(n):
if flag[i] == 1:
flag_sum += score[i]
score[i] = 0
Max = 0
for i in range(n-k+1):
SSum = sum(score[i:min(i+k, n)])
Max = max(SSum+flag_sum, Max)
print Max

发表于 2018-09-08 13:41:03 回复(0)

Python

JAson201807292318563

n,k = list(map(int, raw_input().split()))
score = list(map(int, raw_input().split()))
awake = list(map(int, raw_input().split()))

record = 0
temp = 0
blank = map(lambda x,y: x-x*y, score, awake)#calculate sleeping score

for i in range(n):
if blank != 0 and i <= len(blank)-k:
temp = sum(blank[i:i+k])
if temp > record:
record = temp
temp = 0

score1 = sum(map(lambda x,y: x*y, score, awake))
print score1+record

编辑于 2018-09-01 02:55:25 回复(0)