最佳牛围栏(0x04 二分)

简介: 笔记

最佳牛围栏


题意

农夫约翰的农场由 N 块田地组成,每块地里都有一定数量的牛,其数量不会少于 1 头,也不会超过 2000 头。


约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。


围起区域内至少需要包含 F 块地,其中 F 会在输入中给出。


在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。


思路

原题意为:求一个平均数最大的,长度不小于 F 的连续子段


二分答案,判断是否存在一个长度不小于 F 的子段,其平均值不小于二分的值


若将此区间元素都减去二分的值,问题即转变为:判断是否存在一个长度不小于 F 的子段,子段和非负


下面说明这一题为什么可以二分,假设最优值为 S ,二分的值为 mid,若mid <= S,说明可以找到一个长度不小于 F 的连续子段,平均值为 mid ,否则一定找不到。


对于二分,二分是二分性而不是单调性 只要满足可以找到一个值一半满足条件一半不满足条件即可 而不一定必须满足单调性


所以可以使用二分。


接下来讨论如何求一个子段,它的和最大,且长度大于等于 F44.png

代码

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
const int N = 1e5 + 10;
int n, f; 
double a[N], sum[N], b[N];
void solve() {
  cin >> n >> f;
  for (int i = 1; i <= n; ++i)cin >> a[i];
  double l = 0, r = 2100;
    // 二分答案
  while (r - l > 1e-5) {
    double mid = (l + r) / 2;
    for (int i = 1; i <= n; ++i)b[i] = a[i] - mid;
    for (int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + b[i];
    // 求最大子段和
    double minn = INF, res = 0.0;
    for (int i = f; i <= n; ++i) {
      minn = min(minn, sum[i - f]);
      res = max(res, sum[i] - minn);
    }
    if (res > 0.0)l = mid;
    else r = mid;
  }
  cout << int(r * 1000) << endl;
}
signed main() {
  // int t; cin >> t;
  // while (t--)
    solve();
  return 0;
}


目录
相关文章
【动态规划】【树形dp】【深度优先搜索】LCP 26. 导航装置
【动态规划】【树形dp】【深度优先搜索】LCP 26. 导航装置
|
6月前
|
人工智能 BI
区间问题之区间选点
区间问题之区间选点
|
6月前
|
算法 测试技术 算法框架/工具
【深度优先搜索】【图论】【推荐】332. 重新安排行程
【深度优先搜索】【图论】【推荐】332. 重新安排行程
|
6月前
|
机器学习/深度学习 测试技术
【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离
【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离
|
6月前
|
存储 算法 程序员
【算法训练-搜索算法 一】【DFS网格搜索框架】岛屿数量、岛屿的最大面积、岛屿的周长
【算法训练-搜索算法 一】【DFS网格搜索框架】岛屿数量、岛屿的最大面积、岛屿的周长
122 0
|
算法 Python
算法怎么算:二分为什么是闪电?
代码实现 这里我使用了两种方式,感兴趣的同学可以用更多的方式自己尝试。
31 0
|
算法
贪心算法——区间选点
贪心算法——区间选点
107 0
|
人工智能 BI
【贪心策略】区间选点问题
【贪心策略】区间选点问题
61 0
|
机器人
二分法求机器人跳跃问题
二分法求机器人跳跃问题
95 0
|
人工智能 算法 BI
贪心算法——区间选点与最大不相交区间数
贪心算法——区间选点与最大不相交区间数
68 0