网址导航建站,wordpress提示更新失败,中国最大的电商平台是哪家,杭州网站建设网Best Cow Fences
poj 2018
题目大意#xff1a;
给出一个正整数数列#xff0c;要你求平均数最大#xff0c;长度不小于M的字串#xff0c;结果乘1000取整
输入样例
10 6
6
4
2
10
3
8
5
9
4
1输出样例
6500数据范围 1⩽N⩽100,0001\leqslant N \leqslant 100,0001⩽…Best Cow Fences
poj 2018
题目大意
给出一个正整数数列要你求平均数最大长度不小于M的字串结果乘1000取整
输入样例
10 6
6
4
2
10
3
8
5
9
4
1输出样例
6500数据范围
1⩽N⩽100,0001\leqslant N \leqslant 100,0001⩽N⩽100,000
解题思路
我们先想一想如何求一个长度不小于M且和最大的字段我们可以设两个值num和minn分别表示结果和前面减去的最小值 我们图文结合如下图当n为5M为2 我们先枚举i从m到n表示当前字段的结尾位置因为长度不能小于M所以红色部分是必须选的然后前面的黄色部分是可选可不选的我们到每一个位置时就更新一遍就相当于求一个和最小的字段然后到时直接用sum[i]前缀和减去它就可以更新num了 因为他求的是平均值最大的所以我们每次把所有数减去我们二分得到的结果然后看一看所得的num是否是非负数如果是就说明可以找到这样的一个字段否则没有
代码
#includecstdio
#define min(a,b) (a)(b)?(a):(b)
#define max(a,b) (a)(b)?(a):(b)
using namespace std;
int n,m;
double l,r,mid,num,minn,a[100500],sum[100500];
int main()
{scanf(%d %d,n,m);for(int i1;in;i)scanf(%lf,a[i]);l-1e6;r1e6;while(r-l1e-5){mid(lr)/2;//二分for (int i1;in;i)sum[i]sum[i-1]a[i]-mid;//求前缀和num-1e10;minn1e10;for(int im;in;i){minnmin(minn,sum[i-m]);//计算减去的最小是多少nummax(num,sum[i]-minn);//计算结果}if(num0) lmid;//判断是否存在else rmid;}printf(%d,(int)(r*1000));
}
