[编程题]瞌睡
- 热度指数：34506 时间限制：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
主要思想是将知识点分值化为两部分来分别计算，一部分为保持清醒的时段，此时段的知识点分值固定不受叫醒时间影响；另一部分为根据叫醒时间额外增加的分值，遍历所有可能被叫醒的点，并计算出从该点开始后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
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)
问题信息
通过挑战的用户
查看代码-
2022-09-09 22:16:41
-
2022-09-01 17:15:18 -
2022-09-01 16:37:32 -
2022-08-20 11:02:36
-
2022-08-14 13:42:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
