首页 > 试题广场 >

瞌睡

[编程题]瞌睡
  • 热度指数：34288 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。

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


输出描述:
小易这堂课听到的知识点的最大兴趣值。
示例1

输入

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

输出

16
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 14:30:01
精华题解 题目难度：二星考察点：贪心、前缀和 方法1：暴力算法 分析：我们首先可以通过一次遍历获取小易醒着时所获得的知识点分值，即时所获得的分值，由于题目要求我们只需要进行一次叫醒活动，那么我们就选择当前小易是睡着即的时刻进行往后k个枚举，循环n次即可，然后每次枚举判断其是否为知识点分的最大值。 算法实现 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 laglangyue
发表于 2020-05-17 21:55:43
滑动窗口：因为只要最大得分，只要保存窗口内的得分即可。根据当前i与i+m的sleep状态，更新滑动窗口内的得分，一次遍历即可。 import java.util.Scanner; public class Main { public static void main(String[] ar 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Ⅲ_Dc
发表于 2022-03-07 13:06:03
#include<iostream> #include<stdio.h> #include<vector> using namespace std; int main(void) { int n,k; cin>>n>>k; 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 PHP工程师 贪心 网易 2019 数学 Java工程师
来自：网易2019秋季校园招...
上传者：小小
难度：
125条回答 22220浏览

热门推荐

通过挑战的用户

查看代码

相关试题

瞌睡

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号