当前位置:网站首页>102. 最佳牛围栏
102. 最佳牛围栏
2022-08-03 16:47:00 【Hunter_Kevin】
题目
农夫约翰的农场由 N 块田地组成,每块地里都有一定数量的牛,其数量不会少于 1 头,也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地,其中 F 会在输入中给出。
在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N 和 F,数据间用空格隔开。
接下来 N 行,每行输入一个整数,第 i+1 行输入的整数代表第 i 片区域内包含的牛的数目。
输出格式
输出一个整数,表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。
数据范围
1≤N≤100000
1≤F≤N
输入样例:
10 6
6
4
2
10
3
8
5
9
4
1
输出样例:
6500
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int num[N];
double sum[N];
int n, m;
bool check(double avg){
// 计算减掉平均值的前缀和
// 针对平均值avg计算出的前缀和
for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + num[i] - avg;
double mmin = 0;//记录i位置前的最小值
// sum[j]-sum[i]即i~j的总和,如果sum[j]-sum[i]>=0,则说明长度为j-i的序列的总和>=0
// 即长度至少为m的序列减去平均值avg之后的和大于0,如果有满足此条件的j和i,则说明平均值avg是满足条件的
for(int i = 0, j = m; j <= n; j++, i++){
mmin = min(mmin, sum[i]);
if(sum[j] - mmin >= 0) return true;
}
return false;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)scanf("%d", &num[i]);
// 对给定的范围进行浮点数二分查找结果
double l = 1, r = 2000;
while(r - l > 1e-5){
double mid = (l+r)/2;
if(check(mid))l = mid;
else r = mid;
}
printf("%d\n",int(r*1000));
return 0;
}
边栏推荐
猜你喜欢
随机推荐
Web3 安全风险令人生畏?应该如何应对?
[Unity Getting Started Plan] Basic Concepts (6) - Sprite Renderer Sprite Renderer
[Unity Starter Plan] Making RubyAdventure01 - Player Creation & Movement
leetcode:189. 轮转数组
C专家编程 第2章 这不是Bug,而是语言特性 2.1 这关语言特性何事,在Fortran里这就是Bug呀
2年开发经验去面试,吊打面试官,即将面试的程序员这些笔记建议复习
【Metaverse系列一】元宇宙的奥秘
Hannah荣获第六季完美童模全球总决赛全球人气总冠军
中小微企业如何简单便捷、低成本实现数字化?360视觉云有妙招
protobuf 反射使用总结
【数据库数据恢复】SqlServer数据库无法读取的数据恢复案例
CPU个数_核心数_线程数之间的关系
C专家编程 第1章 C:穿越时空的迷雾 1.11 轻松一下---由编译器定义的Pragmas效果
最强分布式锁工具:Redisson
C专家编程 第2章 这不是Bug,而是语言特性 2.4 少做之过
SwinIR实战:详细记录SwinIR的训练过程
C专家编程 第1章 C:穿越时空的迷雾 1.7 编译限制
LeetCode·72.编辑距离·动态规划
node connection mongoose database process
兄弟组件通信context