1 条题解
-
4唐潍州 (2022ts126) LV 6 @ 2023-1-26 11:36:28
~能过~
#include <stdio.h> #include <stdlib.h> #define MAX(a,b) (a>b?a:b) int main() { int n, m, max=0, head=0, tail=0; int i,j; scanf("%d%d",&n,&m); int *sum = (int*)calloc(n+1, sizeof(int)); int *temp = (int*)calloc(n+1, sizeof(int)); temp[tail++] = 0; //输入数组,改造为前缀和数组 for(i=1; i<=n; i++) { scanf("%d",&sum[i]); sum[i] += sum[i-1]; } for(i=1; i<=n; i++) { j = sum[i]-sum[temp[head]]; //求区间和 max = MAX(max,j); //比较 while(tail-head && sum[i]<sum[temp[tail-1]]) tail--; temp[tail++] = i; if(i - temp[head] == m) head++; //子序列超过范围,最小值过期 } printf("%d",max); return 0; }
- 1
信息
- ID
- 46
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 142
- 已通过
- 54
- 上传者