蒟蒻求助!!
查看原帖
蒟蒻求助!!
230580
Suzt_ilymtics楼主2020/8/30 15:57

我采用的思想类似于贪心,相关解释都在代码里,但不知道为什么WA了第2、3个点

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=5e5+6;
int n,k,x,wz,sum,mmax;
int a[maxn];
int main()
{
	//freopen("P1714_2.in","r",stdin);
	//freopen("P1714.out","w",stdout);
	scanf("%d%d",&n,&k);	
	for(int i = 1; i <= n; ++i ) {
		scanf( "%d" , &a[i] ); 
	}
	sum = a[1]; mmax = a[1]; wz = 1 ;//从第一个数开始求 ,wz代表sum所代表的序列的第一个元素的位置 
	for(int i = 2; i <= n; ++i ) {
		if(wz == i - k ){//如果sum所代表的序列超出长度k,就减去sum所代表的序列的第一个 
			sum -= a[wz];
			wz++;
		}
		if( sum < 0 ){//如果sum所代表的序列和<0,就全部舍弃,并重新标记sum序列的第一个位置 
			sum = 0;
			wz = i;
		}
		sum += a[i];//加上第i个数的幸运值 
		mmax = max ( mmax , sum );//更新 
	//	printf( "%d %d %d %d \n" , i , mmax , i-wz ,sum );
	}
//	cout << endl << a[9831];
}
2020/8/30 15:57
加载中...