廊坊做网站多少钱,福建建设银行招聘网站,跨境电子商务是干什么的,wordpress怎样用最大均值
ybtoj 二分-1-3
题目大意
给出一个序列#xff0c;让你求一个长度不小于m的子序列#xff0c;使其平均值最大
输入样例
10 6
6
4
2
10
3
8
5
9
4
1输出样例
6500数据范围 1⩽L⩽N⩽1051\leqslant L \leqslant N \leqslant 10^51⩽L⩽N⩽105 Ai⩽2000A_i\leqs…最大均值
ybtoj 二分-1-3
题目大意
给出一个序列让你求一个长度不小于m的子序列使其平均值最大
输入样例
10 6
6
4
2
10
3
8
5
9
4
1输出样例
6500数据范围
1⩽L⩽N⩽1051\leqslant L \leqslant N \leqslant 10^51⩽L⩽N⩽105 Ai⩽2000A_i\leqslant 2000Ai⩽2000
解题思路
二分平均值然后用数组存下所有数对当前平均值的贡献 然后判断是否有长度大于L的序列贡献值大于0
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
#define max(x, y) (x)(y)?(x):(y)
#define min(x, y) (x)(y)?(x):(y)
using namespace std;
ll n, m;
double l, r, mid, a[N], sum[N];
bool check(double g)
{for (int i 1; i n; i)sum[i] sum[i - 1] a[i] - g;double ans -2000.0 * N, minn 2000.0 * N;for (int i m; i n; i)//求长度不小于L的序列贡献值最大是多少{minn min(minn, sum[i - m]);ans max(ans, sum[i] - minn);}return ans 0;//大于0
}
int main()
{scanf(%lld%lld, n, m);for (int i 1; i n; i)scanf(%lf, a[i]);l 0;r 2001.0;while(l 1e-5 r)//二分{mid (l r) / 2;if (check(mid)) l mid;else r mid;}printf(%lld, (ll)(r*1000));return 0;
}
