清北学堂模拟赛d2t4 最大值(max)

题目描述
LYK有一本书，上面有很多有趣的OI问题。今天LYK看到了这么一道题目：
这里有一个长度为n的正整数数列ai(下标为1~n)。并且有一个参数k。
你需要找两个正整数x,y，使得x+k<=y，并且y+k-1<=n。并且要求a[x]+a[x+1]+…+a[x+k-1]+a[y]+a[y+1]+…+a[y+k-1]最大。
LYK并不会做，于是它把题扔给了你。

输入格式(max.in)
第一行两个数n，k。
第二行n个数，表示ai。

输出格式(max.out)
两个数表示x,y。若有很多种满足要求的答案，输出x最小的值，若x最小仍然还有很多种满足要求的答案，输出y最小的值。

输入样例
5 2
6 1 1 6 2

输出样例
1 4

对于30%的数据n<=100。
对于60%的数据n<=1000
对于100%的数据1<=n<=100000，1<=k<=n/2，1<=ai<=10^9。

分析：一个O(n^3)的做法，直接枚举两个区间，再枚举求区间和.因为用到了区间和，所以可以用前缀和优化到O(n^2).然后可以发现这个区间长度是固定的，我们可以在挪动右端点的时候右边每加一个数，左边弹一个数，用O(n)的时间处理出每一段长度为k的区间的和，在处理的过程中可以顺便记录j-k之前的区间最大值，一边求和一边统计答案就可以了.

#include <bits/stdc++.h>

using namespace std;

int n,k,lastt = ,x,y;

long long a[],r[],Max,sum,ans;

int main()

{

    freopen("max.in","r",stdin);

    freopen("max.out","w",stdout);

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

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

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

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

    {

        sum += a[i];

        if (i - k > )

            sum -= a[i - k];

        r[i] = sum;

        if (i - k > )

        {

            if (Max < r[i - k])

            {

                Max = max(Max,r[i - k]);

                lastt = i - k;

            }

        }

        if (Max + r[i] > ans)

        {

        ans = max(ans,Max + r[i]);

        x = max(,lastt - k + );

        y = max(,i - k + );

        }

    }

    printf("%d %d\n",x,y);

    return ;

}

巴特西

清北学堂模拟赛d2t4 最大值(max)

最新文章

热门文章