#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e5+10;
int n, m, a[N], s[N];
double f[N];
bool check(double x)
{
for (int i = 1; i <= n; i++)
f[i] = f[i-1]+a[i]-x;
for (int i = m; i <= n; i++)
if (f[i] >= s[i-m]) return true;
return false;
}
int main()
{
std::cin >> n >> m;
for (int i = 1; i <= n; i++)
std::cin >> a[i], s[i] = s[i-1]+a[i];
double l = 1, r = s[n]*1./m;
while (r-l > 1e-5)
{
double mid = (l+r)/2;
if (check(mid)) l = mid;
else r = mid;
}
std::cout << int(r*1000) << "\n";
return 0;
}
题目描述:
在人类和昆虫之间的战争中,人们发现了许多行为模式,并认识到其中一些自己的模式。作为危机时期的指挥官,余教授也发现了一些有趣的模式。例如,指挥官总是喜欢并希望与他们最信任的指挥官合作。因此,如果我们可以自由选择一个指挥官,将其编号为1,让他从剩下的指挥官中选择他最信任的人,然后给他编号2。编号2然后从剩余的指挥官中选择他最信任的人并指派编号3··依此类推。接着,我们可以从这个序列中提取出一个连续的子序列,这个子序列必须具有持续的信赖关系。这正是余教授所希望的!
假设我们有N个指挥官,从1到N排列,每个指挥官都有自己的团队规模。我们希望从他们中提取不少于M名指挥官的连续序列,以便最大化提取的指挥官团队中的人数平均值。
现在,余教授希望你,明智的指挥官,能够帮助他完成这个任务。
输入格式:
第一行输入两个数字N和M(1<N,
M<100000)。
接下来的N行每行输入一个非负数,表示第N个指挥官的部队数量。
输出格式:
输出一个整数,表示最大平均值乘以1000。