首页 > 试题广场 >

瞌睡

[编程题]瞌睡

热度指数：34510 时间限制：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

输出

算法知识视频讲解

JavaScript

一只骑单车的猫

JavaScript 100%通过

let line1 = readline().split(' '),
    line2 = readline().split(' ').map(Number),
    line3 = readline().split(' '),
    n = parseInt(line1[0]),
    k = parseInt(line1[1]);

let count = 0,
    maxZeroCount = 0,
    ZeroCount = 0,
    left=0,
    right=0;
line3.forEach( (ele,index)=> {
    if(ele == 1){
        count += line2[index];
    }else{
        let edge = index + k;
        if(edge > n ) {edge = n};
        // 第一次计算,以及当left==right相等时计算，
        // 因为此时k长度内只有一个‘瞌睡’，下一阶段需要重新计算。
        if(left == right){
            left = index;
            ZeroCount=0;
            for(let i=left;i< edge;i++){
                if(line3[i] == 0){
                    ZeroCount += line2[i];
                    right = i;
                }
            }
        }else{
            // 当left!=right时，表明在k长度内，至少有两个‘瞌睡’，多出的‘瞌睡’
            // 必然会被下一个k长度计算,所以，可以借此获得两个相邻k长度的交叉范围的值。
            // 因此，计算下一个k长度时，只需计算余下部分，节省了运算时间。
            ZeroCount -=line2[left];
            left = index;
            for(let i=right+1;i< edge;i++){
                if(line3[i] == 0){
                    ZeroCount += line2[i];
                    right = i;
                }
            }
        }
        maxZeroCount = Math.max(maxZeroCount,ZeroCount);
    }
});
console.log(maxZeroCount + count);

发表于 2019-08-01 03:33:46 回复(0)