首页 > 试题广场 >

瞌睡

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

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


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

输入

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

输出

16

主要思想是将知识点分值化为两部分来分别计算,一部分为保持清醒的时段,此时段的知识点分值固定不受叫醒时间影响;另一部分为根据叫醒时间额外增加的分值,遍历所有可能被叫醒的点,并计算出从该点开始后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)
"""
思路:从左到右遍历,比较k长度内睡着0状态对应兴趣值的和,即叫醒一下提升的兴趣值。
    总值分为两部分:醒着的固定值 + 睡着的提升值的最大值
"""
n,k =list(map(int, input().split()))
values =list(map(int, input().split()))
awakes =list(map(int, input().split()))
#n,k = [6,3]
#values = [1, 3, 5, 2, 5, 4]
#awakes = [1, 1, 0, 1, 0, 0]
 
base_score =0
for i in range(n):
    if awakes[i]:
        base_score += values[i]
        values[i] =0
         
max_boost_score =0
for i in range(n):
    if not awakes[i]:
        boost_score =sum(values[i:min(i+k,n)])
        max_boost_score =max(boost_score,max_boost_score)
        # 加了下面的break语句,才使这个代码时间上终于达标
        # 扫描到距结尾不足k距离范围内的第一个睡着状态即可,后面的肯定不如这个的提升值大,没必要再跑,可提前结束
        ifi > n-k+1:
            break
         
score =base_score +max_boost_score
print(score)
编辑于 2018-08-15 16:44:17 回复(19)
#include <iostream>
#include <vector>
 
using namespace std;
 
// 连续k个中0对应的最大和, 才是叫醒额外获取的时间
 
int process(const vector<int> & interest, const vector<int> & aweak, int k) {
    int max_scores = 0;
    int scores = 0;
    // 叫醒k分钟
    k = min(k, (int)interest.size()); // 最多能清醒这么长
    // 先计算前k个的零和
    for (int i = 0; i < k; ++i) {
        if (0 == aweak[i]) {
            scores += interest[i];
        }
    }
    // 将k数组往后移动
    max_scores = scores;
    for (int i = k; i < interest.size(); ++i) {
        if (0 == aweak[i]) {
            scores += interest[i];
        }
        if (0 == aweak[i - k]) {
            scores -= interest[i - k];
        }
        max_scores = max(max_scores, scores);
    }
    return max_scores;
}
 
int main() {
    int n = 0; // 共几分钟
    int k = 0; // 叫醒能清醒K分钟
    while (cin >> n >> k) {
        vector<int> interest(n);
        vector<int> aweak(n);
        int scores = 0;
        for (int i = 0; i < n; ++i) {
            cin >> interest[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> aweak[i]; // is aweak?
        }
        // 叫醒k分钟
        scores = process(interest, aweak, k);
        for (int i = 0; i < n; ++i) {
            scores += interest[i] * aweak[i];
        }
        cout << scores << endl;
    }
    return 0;
}

编辑于 2018-08-14 12:26:57 回复(10)
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int cLength = sc.nextInt();//这节课的时长:分钟数
        int lLength = sc.nextInt();//提醒一次能清醒的分钟数
        int [] sumAll = new int[cLength + 1];//表示每分钟所有兴趣点相加
        int [] sumBefore = new int[cLength + 1];//表示有效(醒着)的兴趣值相加
        int maxInterst = 0;//叫醒后产生的最大听课效益
        int sub;//表示 叫醒后lLength分钟的兴趣点 - 之前 llength分钟xing'qu'dia
        int[] intrests = new int[cLength];
        int[] isSleep = new int[cLength];
        for (int i = 0; i < cLength; i++) {
            intrests[i] = sc.nextInt();
            sumAll[i + 1] += intrests[i] + sumAll[i];
        }

        for (int k = 0; k < cLength; k++) {
            isSleep[k] = sc.nextInt();
            if (isSleep[k] == 1)
                sumBefore[k+1] += sumBefore[k] + intrests[k];
            else
                sumBefore[k+1] =sumBefore[k];
        }
        /*以上为输入环节*/

        //边界条件
        if(lLength >= cLength) {
            System.out.println(sumAll[cLength]);
            return;
        }
        if(lLength < 1){
            System.out.println( sumBefore[cLength]);
            return;
        }

        // 1<= llength <clength
        for (int i = 0 ;i < cLength; i++){
            // 提醒后 清醒的时间段 在上课时间内,就是提醒效果在上课时间内有效
            if (i + lLength -1 < cLength && isSleep[i] == 0){
                sub = (sumAll[i +lLength] - sumAll[i]) - (sumBefore[i +lLength] - sumBefore[i]);
                if(sub > maxInterst)
                    maxInterst = sub;
            //提醒效果还有,但是已经下课了。
            }else if (i + lLength -1 >= cLength && isSleep[i] == 0){
                sub = (sumAll[cLength] - sumAll[i]) - (sumBefore[cLength] - sumBefore[i]);
                if(sub > maxInterst)
                    maxInterst = sub;
            }
        }
        System.out.println(maxInterst + sumBefore[cLength]);
    }
}

发表于 2019-08-01 22:23:30 回复(0)

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)
"""
base_score 为清醒时对兴趣度a的求和
max_score 为叫醒一次,k时间内最大的兴趣度
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n, k = list(map(int, input().strip().split()))
    a = list(map(int, input().strip().split()))
    t = list(map(int, input().strip().split()))
    base_score = 0
    for i in range(n):
        if t[i]:
            base_score += a[i]
            a[i] = 0
    max_score = tmp = sum(a[:k])
    for i in range(k, n):
        tmp = tmp + a[i] - a[i - k]
        max_score = max(max_score, tmp)
    ans = base_score + max_score
    print(ans)

发表于 2019-07-03 11:36:50 回复(0)

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)
#include<iostream>
#include<vector>
#include<algorithm>
//总分数分为两部分:已经是清醒的分数 + 睡着的那部分如果清醒时带来的最大分数
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int temp;
    vector<int >score(n,0);
    vector<int >awake(n,0);
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        score[i]=temp;
    }
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        awake[i]=temp;
    }
    long sum=0,maxSum=0,baseSum = 0;
    //计算基本分数
    for(int i=0;i<n;i++)
    {
        if(awake[i])
        {
            baseSum+=score[i];
            score[i]=0;//把清醒取得的分数置0
        }
    }
    //若k大于等于n,则全部分数相加即可
    if(k>=n)
    {
        for(int i=0;i<n;i++)
        {
            maxSum+=score[i];
        }
    }
    //否则,滑动窗口,请窗口分数最大值
    else
    {
        for(int j=1;j<n-k+1;j++)
        {
            sum = 0;
            for(int kk=j;kk<j+k;kk++)
            {
                sum+=score[kk];
            }
            if(maxSum<sum)
                maxSum = sum;
        }
    }
    //输出两部分分数总和
    cout<<maxSum+baseSum;
    return 0;
}

编辑于 2018-08-17 12:05:00 回复(1)
 import java.util.Scanner;

public class aaa {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n;
        int k;
        while (s.hasNext()) {
            n = s.nextInt();
            k = s.nextInt();
            int max = 0;//被重新叫醒后可得的最高分。
            int sum = 0;//表示总的分数
            int[] a = new int[n];
            int[] t = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = s.nextInt();
            }

            int now = 0;
            for (int i = 0; i < n; i++) {
                t[i] = s.nextInt();
                now += t[i] * a[i];
            }

            int res = now;
            for (int i = 0; i < n; ) {
                if (t[i] == 0) {
                    now += 1 * a[i];
                }
                if (++i >= k) {
                    res = Math.max(res, now);
                    if (i-k<n&&i-k>=0) {
                        if (t[i-k] == 0) {
                            now -= 1 * a[i-k];
                        }
                    }
                }

            }
            System.out.println(res);

        }


    }
}
发表于 2018-08-19 13:09:55 回复(1)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    int a[n],b[n],s=0;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++){
        cin>>b[i];
        if(b[i])
            s += a[i];
    }
    int Max = 0;
    for(int i=0;i<=n-k;i++){
        int t = 0;
        for(int j=0;j<k;j++)
            if(b[i+j]==0)
                t += a[i+j];
        Max = max(Max, t);
    }
    cout<<s+Max<<endl;
    return 0;
}

发表于 2019-11-06 01:06:17 回复(0)
# 超简单答案,复杂度为O(n),By Dante
nk = list(map(int,input().split()))
n = nk[0]
k = nk[1]
a = list(map(int,input().split()))
t = list(map(int,input().split()))

max = 0 #记录前k个瞌睡叫醒后兴趣的最大值
for i in range(k):
    if(t[i]==0):
        max += a[i]

pos = 0 #记录最大值的位置
pre = 0 #记录窗口移动过程中最后一个元素位置
cur = max  #当前窗口内的兴趣值
for i in range(k,n):
    if(t[pre]==0):  #元素过期
        cur -= a[pre]
    if(t[i]==0):
        cur += a[i]
    pre += 1
    if(cur>max):
        max=cur
        pos=i

sum=0  #记录清醒状态下的和
for i in range(n):
    if(t[i]==1):
        sum+=a[i]
print(sum+max)
编辑于 2019-08-01 09:54:35 回复(1)
/*
总分值=原本醒得的分值+叫醒他额外得到的分值。
额外得到的分值:单纯的遍历会超时。
这里用了一个队列的思想,进一个,出一个。
*/
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] fun = new int[n];
        int[] sleep = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            fun[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            sleep[i] = in.nextInt();
            if (sleep[i] == 1) {
                ans += fun[i];
            }
        }
        int cnt = 0;    //醒来得到的兴趣值。
        for (int i = 0; i < n && i < k; i++) {
            if (sleep[i] == 0)
                cnt += fun[i];
        }
        int max = cnt;
        for (int i = 1; i < n; i++) {
            if (sleep[i - 1] == 0) cnt -= fun[i - 1];
            if (i + k - 1 < n && sleep[i + k - 1] == 0)
                cnt += fun[i + k - 1];
            max = Math.max(max, cnt);
        }
        ans += max;
        System.out.println(ans);
    }
}

发表于 2019-06-26 21:09:51 回复(2)

前缀和

很简单,用两个前缀和数组配合一下就可以了。是知识点数组的前缀和,是知识点数组在考虑小易是否清醒时的前缀和。

然后枚举叫醒小易的时机,遍历小易的精神状态数组,如果当前分钟为0,就尝试“课堂叫醒服务”,时间段内利用数组计算区间和,其余时段用数组计算区间和即可。
if __name__ == "__main__":
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    t = list(map(int, input().split()))
    p1, p2 = [0] * n, [0] * n      # 不考虑、考虑t状态的前缀和
    p1[0] = a[0]
    p2[0] = a[0] if t[0] else 0
    for i in range(1, n):
        p1[i] = p1[i - 1] + a[i]
        p2[i] = p2[i - 1] + a[i] if t[i] else p2[i - 1]
    if k == 0&nbs***bsp;sum(t) == n:
        print(p2[-1])       # 叫不醒或者没有睡觉的时候就直接返回
    else:
        ans = 0
        for i in range(n):
            if t[i] == 0:
                if i == 0:
                    ans = max(ans, p1[k - 1] + p2[-1] - p2[k - 1])
                else:
                    if i + k - 1 < n:
                        ans = max(ans, p2[i - 1] + (p1[i + k - 1] - p1[i - 1]) + p2[n - 1] - p2[i + k - 1])
                    else:
                        ans = max(ans, p2[i - 1] + p1[-1] - p1[i - 1])
                        
        print(ans)

发表于 2022-04-11 15:49:25 回复(0)
//对于清醒时刻不需要处理,只处理睡着的时候(wake为0),每次计算在这一分钟前和
//连续k分钟内、以及i+k分钟以后的清醒时刻的分数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int hobby[N],wake[N],sum[N],sum1[N];//sum[i]表示前i项和,sum1[i]表示前i项所有清醒时的分数和
int main(){
    int n,k,ans = 0,tmp=0;
    cin>>n>>k;
    for(int i = 1;i<=n;i++){
        cin>>hobby[i];
        sum[i] = sum[i-1]+hobby[i];//求前n项和
    }
    for(int i = 1;i<=n;i++){//这个循环求前i项清醒时的分数和
        cin>>wake[i];
        if(wake[i]==1)
            sum1[i] = sum1[i-1]+hobby[i];
        else
            sum1[i] = sum1[i-1];
    }

    for(int i = 1;i<=n;i++){
        if(wake[i]==0){
            if(i+k-1<=n){
                tmp += sum[i+k-1]-sum[i-1];//对于所有睡着的时候,即wake[i]等于0的时候开始计算,k分钟以内的和
                tmp += sum1[i];//再加上在第i分钟之前所有的清醒分数
                tmp += sum1[n]-sum1[i+k-1];//再加上从i+k之后的所有清醒和
            }else{
                tmp += sum1[i];
                tmp += sum[n]-sum[i-1];
            }
            ans = max(ans,tmp);//更新ans值
            tmp = 0;
        }
    }
    ans = max(tmp,ans);
    cout<<ans<<endl;
    return 0;
}

发表于 2020-08-24 23:38:26 回复(0)
//滑动窗口解法,遍历一次
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> points(n);
    vector<int> weak(n);
    //deque<int> window;//滑动窗口,使用双端队列,前后都可以pop和push
    int sum=0;
    for(int i=0;i<n;i++) cin>>points[i];
    for(int i=0;i<n;i++)
    {
        cin>>weak[i];
        if(weak[i]) sum+=points[i];//先把清醒状态的评分记录下来
    }
    //判断异常情况
    if(k<=0) 
    {
        cout<<sum<<endl;
        return 0;
    }
    //初始化滑动窗口
    int maxofk=0;//k个数的最大和
    int curofk=0;//当前k个数的和
    for(int i=0;i<k;i++)
    {
        //window.push_back(points[i]);
        if(weak[i]==0)curofk+=points[i];
        maxofk=max(maxofk,curofk);
    }
    int index=k;//index指向滑动窗口的右端的下一位,即将要被加入进来的数
    while(index<n)//开始滑动
    {
        if(weak[index-k]==0)//滑动窗口的左端,将要被抛弃
            curofk-=points[index-k];//window.front();
       // window.pop_front();//左端弹出
        if(weak[index]==0)//滑动窗口右端的下一位
            curofk+=points[index];
        //window.push_back(points[index]);//右端插入
        maxofk=max(maxofk,curofk);//记录滑动窗口种weak[i]=0的最大和
        index++;
    }
    cout<<sum+maxofk<<endl;
    return 0;
}


编辑于 2020-05-25 11:15:19 回复(1)
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)
// 用双端队列来记录窗口内最大值,该题应该是判断在k的窗口内睡觉时间的累加和最大值是多少
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> score(n);
    vector<int> awake(n);
    for(int i=0; i<n; i++){
        cin >> score[i];
    }
    for(int i=0; i<n; i++){
        cin >> awake[i];
    }
    int sum = 0;  //记录本来就有的分数
    for(int i=0; i<n; i++){
        if(awake[i] == 1){
            sum += score[i];
        }
    }
    int windowK = 0, maxNeed = 0;  //windowK 记录窗口内awake[i]是0时的score和,maxNeed全局
    deque<int> qmax;
    for(int i=0; i<n; i++){
        if(awake[i] == 0){
            qmax.push_back(i);
            windowK += score[i];
        }
        if(i-qmax.front() == k){  //只把awake是0时的分数加进去
            windowK -= score[qmax.front()];
            qmax.pop_front();
        }
        if(i >= k-1 && !qmax.empty()){  //维持窗口大小为k
            maxNeed = max(maxNeed, windowK);
        }
    }
    maxNeed += sum;
    cout << maxNeed;
    return 0;
}

编辑于 2020-02-01 00:57:53 回复(0)
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[] interest = new int[n];
        for (int i = 0; i < n; i++) {
            interest[i] = sc.nextInt();
        }
        int[] sleep = new int[n];
        for (int i = 0; i < n; i++) {
            sleep[i] = sc.nextInt();
        }
        sc.close();
              //醒着的兴趣值
        int AweakInterest = 0;
        k = Math.min(k, n);
        for (int i = 0; i < n; i++) {
            AweakInterest += sleep[i] == 1 ? interest[i] : 0;
        }
              //遍历查每次叫醒得到最大的睡着的兴趣值
        int sleepInterest = 0;
        for (int i = k - 1; i < n; i++) {
            int sleepInt = 0;
            for (int j = i; j >= i - k + 1; j--) {
                sleepInt += sleep[j] == 0 ? interest[j] : 0;
            }
            sleepInterest = Math.max(sleepInt, sleepInterest);
        }
        System.out.println(AweakInterest + sleepInterest);
    }
}

发表于 2019-09-01 10:32:23 回复(0)
思路就是找到每个睡着的点,都叫醒试一下,然后用阶段和来加速运算。
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[] a=new int[n];
        int[] t=new int[n];
        //考虑睡着不睡着的阶段和
        int[] sum=new int[n];
        //全部都当作不睡着的阶段和
        int[] sum_all=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0;i<n;i++){
            t[i]=sc.nextInt();
        }
        sum[0]=t[0]==1?a[0]:0;
        sum_all[0]=a[0];
        //提前算出阶段和
        for(int i=1;i<n;i++){
            sum_all[i]=a[i]+sum_all[i-1];
            if(t[i]==1){
                sum[i]=a[i]+sum[i-1];
            }else {
                sum[i] = sum[i - 1];
            }
        }
        if(k>=n){
            System.out.println(sum_all[n-1]);
            return;
        }
        int max=0;
        for(int i=0;i<n;i++){
            if(t[i]==0){
                int res=0;
                int r=Math.min(n-1,i+k-1);
                if(i==0){
                    res+=sum_all[r];
                }else{
                    res+=(sum[i-1]+sum_all[r]-sum_all[i-1]);
                }
                if(i+k-1<n-1){
                    res+=(sum[n-1]-sum[i+k-1]);
                }
                max=Math.max(max,res);
            }
        }
        System.out.println(max>0?max:sum_all[n-1]);

    }
}

发表于 2019-08-01 10:52:24 回复(1)

/*

在输入的时候先把ti=1的ai加和得到小易清醒的收益,然后再考虑ti=0的收益

为了避免在讨论ti=0的情况时还要考虑ti=1的情况,可以在输入时如下处理:

若ti=1 则累加sum+=ai

若ti=0 则构造链表 将ti=0的ai往链表尾部add node

之后只需直接对链表操作即可

(也可以选择构造数组)


初步思想是遍历:

对于链表的第i个元素bi 考虑b(i)+b(i+1)+...+b(i+k-1)总共k个时间单位所对应元素和

将i从第一个元素遍历到链表的最后一个

找出上述k个时间单位对应元素和的最大值max

将max+sum即可得到答案

易知 复杂度达到O(n^2) 对于10^5容易超时


优化方案:

(以下的区间长度指代该区间所覆盖的时间长度 不是元素个数)

本次k个时间单位对应元素和 利用上一次运算得到的k个时间单位对应元素和

我们视k个时间单位为一个区间

易知 每一次运算把上一次运算的区间的左端点向右移动一个元素

右端点并不一定向右移动一个元素 这里比较特殊 若左端点的时间单位是t 则只要时间单位

在区间[t,t+k-1]中的元素都应该被划入该区间中 因此右端点的移动距离是不确定的 需要一个个判断

这里的优化在于 可能在某一次右端点的移动距离会很长(不妨假设这次的移动距离上界为O(n))

则下次就势必会缩短 而且渐进意义上和上一次的右端点移动距离成反比 可以这么理解:

每一次区间移动的过程中 右端点或者继续向右移或者原地不动 如果这次右端点移动的距离是k-2或k-1

等非常接近k的某个值 则下一次右端点移动距离就只有0个或1个或2个或3个(否则会使得区间长度大于k)

故可以实现将O(n^2)的复杂度大幅降低接近O(n)的效果

考虑一种特例:数据大小恰好是10^5 k=10^5 且每个元素对应的ti=0

如果用初步思想遍历 显然会超时 时间复杂度:O((N^2)/2)

但如果采用优化方案 时间复杂度会优化到 O(2*N)

对于其他一般数据来说 同上述 一般只会有少数次的运算会使得右端点移动长度特别长 其余都会大幅减少

故实现优化


注意:

1. 本题最后一个样例是坑 题目已经给定条件k>=1 但最后一个样例的k=0

2. 其实本题的时间复杂度主要消耗在区间右端点的移动上 优化方案目的就是减少右端点

的移动 同时又能实现加和

3. 优化方案中的加和就是:区间和先将区间移动之前的左端点的值减掉 再根据数据将区间右端点右移

区间和加上新加入的元素 即可得到本轮的区间和 然后区间和与max比较 更新max

4. 注意区别k个时间单位所对应的元素 与 k个元素 的区别

*/


Ans:


#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define New(a ,i) (a*)malloc(sizeof(a)*i)

#define Cle(a) memset(a ,0 ,sizeof(a))

#define Inv -1

#define MAX 100000


typedef struct node

{

    int num;

    int key;

    struct node* next;

}node;


node *header=NULL ,*cur=NULL ,*low=NULL ,*high=NULL;

int n=0 ,k=0;

int a[MAX];

int t;

int sum=0 ,max=Inv;


void initial()

{

    header=New(node ,1);

    header->num=header->key=Inv;

    header->next=NULL;


    cur=low=high=header;

}


void add(int ti ,int key)

{

    node* temp=New(node ,1);

    temp->num=ti;

    temp->key=key;

    temp->next=NULL;

    cur->next=temp;

    cur=temp;

}


void input()

{

    scanf("%d %d" ,&n ,&k);

    Cle(a);


    for(int i=0 ;i<n ;++i)

        scanf("%d" ,&a[i]);

    for(int i=0 ;i<n ;++i)

    {

        scanf("%d" ,&t);

        if(t)    sum+=a[i];

        else

            add(i ,a[i]);

    }

}


int ope()

{

    if(header->next->next == NULL)

        return a[0];


    int ti=k-1;

    int temp=0;

    low=header->next;    high=low->next;


    if(k != 0)  temp+=low->key;


    while(low != NULL)

    {

        while(high && low->num + ti >= high->num)

        {

            temp+=high->key;

            high=high->next;

        }

        max=max<temp ?temp :max;

        temp-=low->key;

        low=low->next;

    }


    return max;

}


int main()

{

    initial();

    input();

    printf("%d", ope()+sum);


    return 0;

}




发表于 2019-07-06 22:04:00 回复(0)