本文共 2019 字,大约阅读时间需要 6 分钟。
小易觉得高数课太无聊了,决定睡觉。不过他对课上的一些内容挺感兴趣,所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度,并以分数量化,以及他在这堂课上每分钟是否会睡着,你可以叫醒他一次,这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。
第一行 n, k (1 <= n, k <= 10^5) ,表示这堂课持续多少分钟,以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数,a1, a2, ... , an(1 <= ai <= 10^4) 表示小易对每分钟知识点的感兴趣评分。 第三行 n 个数,t1, t2, ... , tn 表示每分钟小易是否清醒, 1表示清醒。
小易这堂课听到的知识点的最大兴趣值
6 3
1 3 5 2 5 4 1 1 0 1 0 0
16
每分钟都会有两个量,一个是小易对这一分钟知识点的感兴趣评分,以及小易是否清醒,输入的k为叫醒小易后他能保持清醒的时间,只能叫醒小易一次,要求得出小易这堂课听到的知识点的最大兴趣值。
方法一:最先想到的就是一个很暴力的方法,先求出小易醒着的的兴趣值总和sum,然后从头开始遍历每一分钟,判断是否清醒,如果为不清醒,那么就遍历接下来k个值,把这k个值未醒着的分值加到前面的sum上,与记录的最大的兴趣值比较并不断更新最大值。但是这个绝对就会超时,确实超时了。
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int k=in.nextInt(); int[] value=new int[n]; //知识点的兴趣值 int[] wake=new int[n]; //每分钟是否清醒 for(int i=0;imax)max=m; } } System.out.println(max); }}
方法二:可以定义3个数组,长度都为n。leftv数组是表示从左边开始到右清醒时兴趣值的累加和,rightv数组是表示从右边开始到左清醒时兴趣值的累加和,tolv表示从左到右所有兴趣值的累加和。
然后当我们遍历到为未醒着的位置i时,那么这时的总的兴趣值为3部分之和:leftv[i-1] + rightv[i+k] + (tolv[i+k-1] - tolv[i-1])。最重要的就是考虑边界问题,第一部分的值为第i分钟左边的值,左边界的问题就是要考虑i-1不能小于0,如果小于0,那么左边的和就不是加leftv[i-1]而是加0,第二部分的值就是第i分钟右边得值,右边界的问题就是要考虑i+k要小于n,如果大于n,那么右边得和就不是加rightv[i+k]而是加0,最后一部分就是i与i+k之间的兴趣值的和,tolv[Math.min(i+k-1, n-1)]-(i<1?0:tolv[i-1]),也是需要考虑边界问题。
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int k=in.nextInt(); int[] value=new int[n]; //知识点的兴趣值 int[] wake=new int[n]; //每分钟是否清醒 for(int i=0;i=0;i--) { if(wake[i]==1)sum+=value[i]; rightv[i]=sum; } int[] tolv=new int[n]; //记录此分钟之前的清醒和未清醒所有的兴趣值 sum=0; for(int i=0;i =n)m+=0; //考虑右边界的问题 else m+=rightv[i+k]; m+=tolv[Math.min(i+k-1, n-1)]-(i<1?0:tolv[i-1]); if(m>res)res=m; } } System.out.println(res); } }}
转载地址:http://cszci.baihongyu.com/