求调，超时27分

题目总版

Newdon @ 2024-11-06 09:25:36

2020GCOI五年级第六题收集数据

题目描述

幼儿园的N名（N为偶数）小朋友们排成一列，每个人手中都拿有一个数据fi，两位老师分别站在队首和队尾。一个从队首往中间走，一位从队尾往中间走，他们俩走的节奏始终一致，直到相遇为止。在行进的过程中，他们每人可以收集连续K个小朋友手上的数据，但必顺在同一时刻开始，同一时刻结束。求这个过程被收集的数据之和最大可能是多少。

输入

输入为数据有两行。

第一行是两个整数N和K，其中N为小朋友的人数， K为两位老师可以收集的连续的数据的个数。第二行有N正整数，依次给出每个小朋友手中的数据fi。

输出

输出为一行，是一个整数，为被收集的小朋友手中数据之和的最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],maxx1=-100,maxx2=-100,sum1,sum2;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n/2-k+1;i++){
        for(int j=i;j<=k+i-1;j++)sum1+=a[j];
        if(sum1>maxx1)maxx1=sum1;
        sum1=0;
    }
    for(int i=n/2+1;i<=n-k+1;i++){
        for(int j=i;j<=k+i-1;j++)sum2+=a[j];
        if(sum2>maxx2)maxx2=sum2;
        sum2=0;
    }
    maxx1+=maxx2;
    printf("%d",maxx1);
    return 0;
}

by Newdon @ 2024-11-06 16:34:28

@c22j33c43

输入

8 2

1 1 5 1 2 4 3 1

by Newdon @ 2024-11-06 16:35:12

@c22j33c43

输出

by c22j33c43 @ 2024-11-06 16:44:07

看看可不可以

#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
int n,a[maxn],b[maxn],mx,a1,b1[maxn],k;
int main(){
    scanf("%d%d",&n,&k);
    int m=n/2;//中点 
    for(int i=1;i<=m;i++){
        scanf("%d",&a1);
        a[i]=a1+a[i-1];//左半部分前缀和 
    }  
    for(int i=m;i>=1;i--) scanf("%d",&b1[i]);//倒置 
    for(int i=1;i<=m;i++) b[i]=b[i-1]+b1[i];//右半部分倒置前缀和  
    for(int i=k;i<=m;i++) mx=max(mx,(a[i]-a[i-k])+(b[i]-b[i-k]));//求最大的解 
    printf("%d",mx);
    return 0;
}

by c22j33c43 @ 2024-11-06 16:45:12

@HRZ_2012

by c22j33c43 @ 2024-11-06 16:47:49

复杂度忽略常数顶破天O(m)

by Newdon @ 2024-11-06 16:50:07

@c22j33c43

dad

by c22j33c43 @ 2024-11-06 16:51:58

我靠，受不起

A了没

by Newdon @ 2024-11-06 16:52:28

@c22j33c43

再问你一题行不？

by Newdon @ 2024-11-06 16:52:53

@c22j33c43

A了

by c22j33c43 @ 2024-11-06 16:53:42

可以