Farmer John's farm consists of a long row of N (1≤N≤100,000) fields. Each field contains a certain number of cows, 1≤ncows≤2000. FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1≤F≤N) fields, where F given as input. Calculate the fence placement that maximizes the average, given the constraint.

输入格式

  • Line 1: Two space-separated integers, N and F.
  • Lines 2..N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on.

输出格式

  • Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000×ncows ÷ nfields .

输入样例:

10 6
6 
4
2
10
3
8
5
9
4
1

输出样例:

6500

题目分析

题目要求:

连续地块数目大于 f, 且平均每块的牛的数目最多, 求这个平均值。

我们可以发现,我们可以二分平均值,再判断平均值是否合法来解决问题。

其中平均值的下界为 1, 上界为 N * n

问题转换为: 有长度限制的最大子段和。

这里可以使用前缀和算法优化时间, 并且在计算前缀和数组的过程中可以将每个数目减去二分出来的平均值。

问题转换为: 有长度限制的最大子段和大于等于 0

通过前缀和的性质:

$$ 下标从 j + 1 到 i 的子段和 = sum[i] - sum[j] (i - j >= f) $$

可以得到:

$$ 有长度限制的最大子段和 = sum[i] - minist(sum[j]) (i - j >= f) $$ 即:

for(int i = f; i <= n; ++i) {
    mini = min(mini, sum[i - f]);
    if(sum[i] >= mini) return 1;
}

代码实现

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

int n , f, cow[N];
bool check(double val) {
    double mini = N * n, sum[N];
    memset(sum, 0, sizeof sum);
    for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + cow[i] - val;
    for(int i = f; i <= n; ++i) {
        mini = min(mini, sum[i - f]);
        if(sum[i] >= mini) 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 >> cow[i];
    double l = 0, r = n * N;
    while(r - l >= 1e-5) {
        double mid = (r - l) / 2 + l;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(r * 1e3);
    return 0;
}

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status