1 条题解

  • 4
    @ 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
    上传者