首页 > 试题广场 >

瞌睡

[编程题]瞌睡
  • 热度指数：34249 时间限制：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
算法知识视频讲解
添加回答
Java
人生寂寞如雪糕头像 人生寂寞如雪糕 
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[] score = new int[n];
		int[] status = new int[n];
		for (int i = 0; i < n; i++) {
			score[i] = in.nextInt();         //读入兴趣点
		}
		int basic = 0;                       //必得分
		for (int i = 0; i < n; i++) {
			status[i] = in.nextInt();        //读入状态
			basic += score[i] * status[i];   //累加必得分
		}
		int extra = 0;                       //叫醒后k分钟内的最大额外分
		for (int i = 0; i < n - k + 1; i++) {
			int temp = 0;                    //第i分钟到i+k分钟的额外分
			for (int j = 0; j < k; j++) {    //计算这一段的额外分
				temp += score[i + j] * (1 - status[i + j]);//核心，只累加额外得分
			}
			extra = extra > temp ? extra : temp;//比较最大额外分
		}
		System.out.print(basic + extra);     //最终得分为基础+额外
	}   //为什么循环到n-k+1就结束了，因为后面时间内的得分不会超过最后一次计算的额外分
}
极简思路
发表于 2020-05-14 23:49:32 回复(0)
Java
橘子想要个offer头像 橘子想要个offer 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] interest=new int[n];
        int[] awake=new int[n];
        long sum1=0;
        for(int i=0;i<n;i++){
            interest[i]=sc.nextInt();
        }
        for(int i=0;i<n;i++){
            awake[i]=sc.nextInt();
            if(awake[i]==1)
                sum1+=interest[i];
        }
        
        int max=0;
        for(int i=0;i<=n-k;i++){
            int sum=0;
            for(int j=0;j<k;j++){
                if(awake[i+j]==0)
                    sum+=interest[i+j];
            }
            if(sum>max)
                max=sum;
        }
        System.out.println(max+sum1);
    }
}
遍历所有清醒时刻的兴趣总和，然后循环遍历k个节点的兴趣和，期间如过i+j节点值为1，表示在第一次计算总和时已经考虑，不予以添加
发表于 2020-04-22 11:58:14 回复(0)
Java
陈。。201901131610494头像 陈。。201901131610494 
package test.alogorithm.test;

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        int time = sc.nextInt();
        int count=0,max=0,temp=0;
        //兴趣评分列表
        int[] a=new int[number];
        for (int i=0;i<number;i++){
            a[i]=sc.nextInt();
        }
        //清醒列表
        int[] b=new int[number];
        for (int i=0;i<number;i++){
            b[i]=sc.nextInt();
        }

        //判断如果叫醒时间大于课堂时间直接计算出所有和
        if (time>=number){
            for (int i=0;i<number;i++){
                count+=a[i];
            }
            System.out.println(count);
        }else {
            //------>    寻找最大值
            for (int i=0;i<number-time;i++){
                if (b[i]==0){
                    for (int j=i;j<i+time;j++){
                        if (b[j]==0) {
                            temp += a[j];
                        }
                    }
                    if (temp>max) max=temp;
                    //注意临时变量的初始化
                    temp=0;
                }
            }
            //直接计算状态为0的值之和的最大值
            for (int i=number-time;i<number;i++){
                if (b[i]==0) {
                    temp += a[i];
                }
                if (max<temp) max=temp;
            }
            //<------    寻找最大值
            //计算出状态为1的值之和
            for (int i=0;i<number;i++){
                if (b[i]==1){
                    count+=a[i];
                }
            }
            //输出加上状态为0的值之和的最大值
            System.out.println(count+max);
        }
    }
}

发表于 2020-04-20 21:01:28 回复(0)
Java
RicharthLee头像 RicharthLee

Java简洁实现 O(n)复杂度

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[][] list  = new int[n][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                list[j][i] = in.nextInt();
            }
        }
        int max = 0;
        for (int i = 0, count = 0; i < n; i++) {
            if(list[i][1] == 0) count += list[i][0];
            if(i-k >= 0 && list[i-k][1] == 0) count -= list[i-k][0];
            max = Math.max(max,count);
        }
        for (int i = 0; i < n; i++) {
            if(list[i][1] == 1) max += list[i][0];
        }
        System.out.println(max);
    }
}
发表于 2020-04-17 11:08:41 回复(0)
Java
Jimmy_Huang头像 Jimmy_Huang 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] a=new int[n];
        int[] t=new int[n];
        int[] sum=new int[2*n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0;i<n;i++){
            t[i]=sc.nextInt();
        }
        for(int i=0;i+k<=n;i++){
            int b[]=new int[n];
            for(int j=i;j<i+k;j++){
                if(t[j]==0){
                    b[j]=1;//记录原先修改前的a[j]的位置;
                    t[j]=1;
                }
            }
            for(int j=0;j<n;j++){
                sum[i]+=a[j]*t[j];
                if(b[j]==1){
                    t[j]=0;//改回原来的数据；
                }
            }
        }
        Arrays.sort(sum);
        System.out.print(sum[sum.length-1]);
    }
}
通关60%，算法复杂度过大！
要是有大神帮忙优化下就万分感激了！
本人的思路是：
6 3
1 3 5 2 5 4
1 1 0 1 0 0
因为k=3;所以3个连续的元素为一个块逐取（135 352 525 254）
然后把选中的块里的t值全改为1；同时记录修改的位置，方便后面重新取时改回来；
然后求块里的值(sum)
最后找到sum的最大值。
发表于 2020-02-25 21:59:06 回复(0)
Java
1+½+¼+⅛+...头像 1+½+¼+⅛+... 
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int k = input.nextInt();
        int a[] = new int[n];
        int t[] = new int[n];
        for(int i = 0; i < n; i++) {
        	a[i] = input.nextInt();
        }
        for(int i = 0; i < n; i++) {
        	t[i] = input.nextInt();
        }
        input.close();
        System.out.println(Solution(n, k, a, t));
        
    }
    
    public static int Solution(int n, int k, int[] a, int[] t) {
    	if(k >= n)
    		return Sum(a);
    	int sum1 = 0;
    	int num0 = n;
    	for(int i = 0; i < n; i++)
    		if(t[i] == 1) {
    			sum1 += a[i];
    			num0 --;
    		}
    	if(num0 < 2)
    		return Sum(a);
    	int sum0[] = new int[num0];
    	int index = 0;
    	for(int i = 0; i < a.length; i++) {
    		if(t[i] == 0) {
    			for(int j = i; j < i + k && j < n; j++) {
    				if(t[j] == 0)
    					sum0[index] += a[j];
    			}
    			index ++;
    		}
    	}
    	int Msum0 = sum0[0];
    	for(int i = 0; i < num0; i++)
    		if(sum0[i] > Msum0)
    			Msum0 = sum0[i];
    	return sum1 + Msum0;		
    }
    
    public static int Sum(int[] a) {
		int sum = 0;
		for(int i = 0; i< a.length; i++) {
			sum += a[i];
		}
    	return sum;
    }
    
}

发表于 2019-09-04 18:34:53 回复(0)
Java
啊啊啊，求offer头像 啊啊啊，求offer
import java.util.Scanner;
public class Main{
    public static void main(String [] args)
    {
        //还是分成几步骤
        //1.读取数据
        //2. 把所有他清醒的时间的知识点算出来
        //然后遍历， 所有剩下的有空的时间的max再相加就好
        
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        int k = sc.nextInt();
        int [] score = new int[n];
        int [] time = new int[n];
        for(int i=0; i<n; i++)
        {
            score[i]= sc.nextInt();
        }
        for(int i=0; i<n; i++)
        {
            time[i]= sc.nextInt();
        }
        int res =0;
        int max =0;
        int max1 = 0;
        for(int i=0; i<n; i++)
        {
            if(time[i]==1)
            {
                res += score[i];
                score[i]=0;            //在取出的时候， 直接将这个时间设为0， 后期就不需要检验了
            }
            if(i<k)
            {
                max1 += score[i];
            }
                
         //   if(time[i]==0)
      /*      else            //这个直接找的方法超时了
            {
                int r = 0;
                for(int j=i;j<n&&j-i<k; j++)
                {
                    if(time[j]==0)
                        r += score[j];
                }
                max = max>r?max:r;
            }*/
        }
        max = max1;
        
        for(int i=k;i<n; i++)
        {
            max1 = max1-score[i-k];    
            max1 = max1+score[i];    
            max = max>max1?max:max1;
        }
        res = res + max;
        System.out.println(res);
        
        
    }
    
}
发表于 2019-09-02 13:51:57 回复(0)
Java
我是渣渣虫头像 我是渣渣虫

主要思想是将知识点分值化为两部分来分别计算，一部分为保持清醒的时段，此时段的知识点分值固定不受叫醒时间影响；另一部分为根据叫醒时间额外增加的分值，遍历所有可能被叫醒的点，并计算出从该点开始后k个点内新增的知识点分，比较各个可叫醒点的该值取最大。需注意的是在求取可叫醒点i的新增知识点分时，若直接再使用循环遍历后面k个点复杂度较高，此处使用一个睡眠点分值的累加数组来进行优化。
图片说明 

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;
    }
}
编辑于 2019-08-02 09:53:44 回复(8)
Java
4K包吃住送电动车保温箱头像 4K包吃住送电动车保温箱

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int minute = sc.nextInt();
            int wakeminute = sc.nextInt();
            int[] interst = new int[minute];
            int[] condition = new int[minute];
            long sum = 0;
            long res=0;
            for (int i = 0; i < minute; i++) {
                interst[i]=sc.nextInt();
            }
            for (int i = 0; i < minute; i++) {
                condition[i]=sc.nextInt();
            }
            for (int i = 0; i < minute; i++) {
                if(condition[i]==1) {
                    sum+=interst[i];
                }
            }
            for(int i=0;i<minute-wakeminute;i++) {
                int temp=0;
                for(int j=i;j<i+wakeminute;j++) {
                    if(condition[j]==0) {
                        temp+=interst[j];
                    }
                }
                res=Math.max(res,temp);
            }
            System.out.println(sum+res);
        }
    }
}

发表于 2019-07-31 10:17:09 回复(0)
Java
Mono_Chrome头像 Mono_Chrome

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] interset = new int[n];
        int[] isAwake = new int[n];
        int[] sumInterestOf0 = new int[n];

        for (int i = 0; i < n; i++) {
            interset[i] = sc.nextInt();
        }

        int sum0 = 0;
        int sum1 = 0;
        for (int i = 0; i < n; i++) {
            isAwake[i] = sc.nextInt();
            if (isAwake[i] == 1) {
                sum1 += interset[i];
            } else {
                sum0 += interset[i];
            }
            sumInterestOf0[i] = sum0;
        }

        int cur = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (isAwake[i] == 0) {
                if (i + k - 1 > n - 1) {
                    cur = sumInterestOf0[n - 1] - (i - 1 >= 0 ? sumInterestOf0[i - 1] : 0);
                } else {
                    cur = sumInterestOf0[i + k - 1] - (i - 1 >= 0 ? sumInterestOf0[i - 1] : 0);
                }
                max = cur > max ? cur : max;
            }
        }
        System.out.println(sum1 + max);
    }
}
发表于 2019-06-30 14:31:11 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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