非正解(单调)O(n2)的程序能过,希望调整数据,谢谢!
查看原帖
非正解(单调)O(n2)的程序能过,希望调整数据,谢谢!
346037
BGmusic楼主2022/9/8 17:21
#include<bits/stdc++.h>
using namespace std;
int n,s,t;
int a[200001];
int pa[200001];
int total=0;
int main()
{
	cin>>n;
	cin>>s>>t;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		pa[i]=pa[i-1]+a[i];
	}
	double ans=-1000000.0;
	for(int i=s;i<=t;i++)
	{          
		for(int j=i;j<=n;j++)
		{
			total++;
			ans=max(ans,(pa[j]-pa[j-i])/(1.0*i));
			if(total>201300001)
			{
				printf("%.3f",ans);
				return 0;
			}
		}
	}
	printf(	"%.3f",ans);
	return 0;
}

@chen_zhe

for循环的极限是216.....? 不超时寻找的“最优解”是答案,有点凑巧了。

希望调整数据,谢谢!

2022/9/8 17:21
加载中...