瞌睡(java版)

编程入门行业动态更新时间:2024-10-11 03:23:17

瞌睡(java版)

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

第一行 n, k (1 <= n, 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

输出

2.思路：
思路1：将醒着的总兴趣值进行相加，然后从0开始遍历，到n-m，计算m长度醒着的总数值存入列表，降序，取出最大值与醒着得到的总兴趣相加，即为总值。但是这样的话时间复杂度太高，通过率60%
思路2：
主要思想是将知识点分值化为两部分来分别计算，一部分为保持清醒的时段，此时段的知识点分值固定不受叫醒时间影响；另一部分为根据叫醒时间额外增加的分值，遍历所有可能被叫醒的点，并计算出从该点开始后k个点内新增的知识点分，比较各个可叫醒点的该值取最大。需注意的是在求取可叫醒点i的新增知识点分时，若直接再使用循环遍历后面k个点复杂度较高，此处使用一个睡眠点分值的累加数组来进行优化。

参考：牛客网
呛呛龙
3.代码：
思路1代码：通过率60%

import java.util.*;public class Awaken {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();HashMap<Integer,Integer> inter_num=new HashMap<>();HashMap<Integer,Integer> bool=new HashMap<>();List<Integer> alarm_sum=new ArrayList<>();for (int i = 0; i <n ; i++) {inter_num.put(i,sc.nextInt());}int nosleep_sum=0;for (int i = 0; i <n ; i++) {bool.put(i,sc.nextInt());}for (int i = 0; i <n ; i++) {if (bool.get(i) == 1) {nosleep_sum+=inter_num.get(i);}}//计算叫醒小易可以得到的知识值for (int i = 0; i <=n-m ; i++) {int sum=0;for (int j = 0; j < m; j++) {if (bool.get(i+j) == 1) {sum=sum+0;}else {sum+=inter_num.get(i+j);}alarm_sum.add(sum);}}if (alarm_sum.size() != 0) {alarm_sum.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}});}int Maxsum=0;if (alarm_sum.size() != 0) {Maxsum  =alarm_sum.get(0)+nosleep_sum;}else {Maxsum=nosleep_sum;}
System.out.println(Maxsum);}
}

思路2 来自牛客网呛呛龙
链接：=discussion
来源：牛客网
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] val = new int[n];
int[] state = new int[n];
//保存瞌睡时的累计评分
int sleep = 0;
int[] sleepval = new int[n];
for(int i=0;i<n;i++){
val[i] = scan.nextInt();
}
for(int i=0;i<n;i++){
state[i] = scan.nextInt();
if(state[i]==0){
sleep += val[i];
}
sleepval[i] = sleep;
}
Main ma = new Main();
int res = ma.getMaxVal(val,state,n,k,sleepval);
System.out.println(res);
}
public int getMaxVal(int[] val,int[] state,int n,int k,int[] sleepval){
int res = 0;
int addval = 0;
for(int i=0;i<n;i++){
if(state[i]==1) res += val[i];
else{
int wakeval = 0;
if(i+k-1>=n){
wakeval =(i>0)?(sleepval[n-1]-sleepval[i-1]):sleepval[n-1];
}else{
wakeval = (i>0)?(sleepval[i+k-1]-sleepval[i-1]):sleepval[i+k-1];
}
addval = addval>=wakeval?addval:wakeval;
}
}
return res+addval;
}
}