一种新的AC思路,求证
  • 板块P1419 寻找段落
  • 楼主walkwp
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/11/14 23:11
  • 上次更新2023/10/27 02:55:39
查看原帖
一种新的AC思路,求证
757752
walkwp楼主2022/11/14 23:11

也AC了,时间也OK,就是想问问各位大佬,有没有人能用数学证明,当使用一个区间N算出了最大平均值且区间增加为N+X时,该最大平均值均没有发生变化,那么不管区间再如何增大,平均值都不可能再发生变化了,并且这个X是可以明确求得的,谢谢。

AC程序如下(预估X值为2000):

#include<bits/stdc++.h>
using namespace std;
int n,s,t,flag,a[100005],ss[100005];
double ans=-10000000;
int main()
{
  cin>>n>>s>>t;
  for (int i=1;i<=n;i++){
  	scanf("%d",&a[i]);
  	ss[i]=ss[i-1]+a[i];
  }  
  for (int i=s;i<=t;i++){
  	for (int j=i;j<=n;j++)
  	  if(double(ss[j]-ss[j-i])/i>ans){ 
		ans=double(ss[j]-ss[j-i])/i;
		flag=i;
    }
    if (i-flag>2000) break;
  }
  printf("%.3f",ans);
  return 0;
}

2022/11/14 23:11
加载中...