农夫约翰的农场由 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

题目分析

首先, 我们估算目标程序的效率。 观察数据范围我们可以看到 max( N ) == 1e5,所以我们的程序需要时间复杂度在 O(n log n)以下才能在 1s内完成相应的测试点。

此题中,我们需要大量的区间和的运算,并且max(牛的数目) == 2000,不用考虑累加之和溢出,所以可以采用使用 前缀和算法 来优化时间

如果我们按照题目的描述,正向枚举合法的连续地块并使用前缀和算法优化的话,我们的时间复杂度很明显为O(n ^ 2),不能满足题目时间限制。所以我们可以考虑逆向思维,逐步减小范围地列举出可能的结果,再判断列举出的结果的合法性,通过范围的不断减小,最终收敛出最终的结果。

综合上述解题思路,我们可以发现,我们可以在输入数据时找到浮点数的二分查找(O(log n)) 的上下界。再通过不断变小的二分查找区间收敛出最终结果。最终的时间复杂度为O(n log n),符合题目时间限制。

需要注意的一些细节是:

  • 由于平均值的最大值要乘以1e3再输出,我们可以根据一般精度规律,将二分查找的界限设置为r - l > 1e-5
  • 最终的输出结果为什么不是 (int)(l * 1e3) ?,因为一定会被向下取整, 如果 r == 1.5000, l = 1.4999, 按照(int)(l * 1e3)最终结果为 1499.0 没有在理想的 1500.0 ~ 1499.9 区间内。而如果我们选择 (int)(r * 1e3)的话,最终结果在理想的区间内的概率相比更高既误差更小。所以我们宁愿选取更大的r

代码实现

#include <iostream>
#include <cstring>
using namespace std;
using db = double;
const int N = 1e5 + 10;

int n, f;
db l, r, arr[N], prs[N];
inline bool check(db mid) {
    memset(prs, 0, sizeof prs);
    for (int i = 1; i <= n; ++i) prs[i] = prs[i - 1] + arr[i] - mid;
    db mins = 0;
    for (int i = f; i <= n; ++i) {
        mins = min(mins, prs[i - f]);
        if (prs[i] >= mins) return 1;
    }
    return 0;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> f;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        l = min(l, arr[i]);
        r = max(r, arr[i]);
    }
    while(r - l > 1e-5) {
        db mid = (r - l) / 2 + l;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(r * 1e3);
    return 0;
} 
分类: Binary-Search

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status