暴力超时代码
这个复杂度是N*N!
1s的时限是不可能AC的
一般算机一秒能运行5 x 10^8次汁算
///给区间长为N的数组,求区间长度大于等于F的数组的总和
#include<cstdio>
#include<algorithm>
int brr[100010],a[100010],ans[100010];
double Ans;
using namespace std;
int main()
{
int N,F;
scanf("%d%d",&N,&F);
for(int i = 1;i <= N;i++)
{
scanf("%d",&a[i]);
brr[i]=brr[i-1]+a[i];//求前缀和
//printf("%d ",brr[i]);
}
int n = 0,j = 0,m = 1;
int f = F;
int Q = F;
double q = (double)F;
for(int k = F;k <= N;k++)//枚举区间F到N的数
{
while(true)
{
//printf("$%d %d\n",f,N);
ans[n++] = brr[f++]-brr[j++];//用前缀和求解
if(f == N+1)
break;
}
f = F+m;
m++;
j = 0;
for(int i = 0;i < n;i++)
{
double w = (double)ans[i]/q;//计算平均值
Ans = max(Ans,w);
}
n = 0;
q++;
}
printf("%.lf\n",Ans*1000);
}
1s的时间只能用二分logN*N的复杂度
把1到2000的可能达到的最大平均值二分,再用N的复杂度去判定它的合法性
步骤:
1.二分可能的答案范围1~2000
2.判断二分的mid是否可能(用2个指针i,j判断区间长度大于等于F的区间总和是否存在大于等于0
sun[j]-sum[i] >= 0
可以j,i然后挑选sum[i]中最小的数,因为存在就行,如果存在大于等于0,return ture。
)
3.取右边界,向下取整
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100010];
double sum[100010];
int N,F;
bool check(double avg)
{
for(int i = 1;i <= N;i++)
sum[i] = sum[i-1]+a[i]-avg;
double min_i = 0;
for(int i = 0,j = F;j <= N;i++,j++)
{
min_i = min(min_i,sum[i]);
if(sum[j]-min_i >=0)
return true;
}
return false;
}
int main()
{
scanf("%d%d",&N,&F);
for(int i = 1;i <= N;i++)
{
scanf("%d",&a[i]);
}
double l = 0,r = 2000;
while(r-l>1e-5)
{
//printf("#%lf\n",r);
double mid = (l+r)/2;
if(check(mid))
l = mid;
else
r = mid;
}
printf("%d\n",int(r*1000));
return 0;
}