AcWing 102. 最佳牛围栏
原题链接
简单
作者:
CqAq
,
2024-04-08 22:13:55
,
所有人可见
,
阅读 4
算法1
(暴力枚举12/15) $O(nlog(n)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 1E5 + 9;
int n, f;
double a[N];
ll ans;
bool check(int x){
if(x < f) return false;
for(int i = 1; i + x - 1 <= n; ++ i) ans = max(ans, (ll)((a[i + x - 1] - a[i - 1]) / x * 1000.0));
return true;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> f;
for(int i = 1; i <= n; ++ i) cin >> a[i], a[i] += a[i - 1];
int l = 1, r = 100005;
while(l < r){
int mid = (l + r) / 2.0;
if(check(mid)) r = mid;
else l = mid + 1;
}
//cout << l << '\n' << r << '\n';
cout << ans;
return 0;
}