POJ2018 Best Cow Fences

发表于 | 分类于 |
字数统计: 301 字

题目地址

题解

这题精度高的一批…
总之想到直接求解比较困难，联想到这样平均值的题目一般要用上二分，所以二分一个最大平均值，然后根据判定条件来就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, L, a[100005], sum[100005], maxi = 0;
void init(){
    n = read(), L = read();
    sum[0] = 0;
    for(int i = 1; i <= n; ++i)
        a[i] = read(), maxi = max(maxi, a[i]), sum[i] = sum[i - 1] + a[i];
}
bool judge(double x){
    double mini = 0;
    for(int i = L; i <= n; ++i){
        double cur = 1.0 * sum[i] - i * x;
        if(cur > mini || abs(cur - mini) < 1e-5)
            return true;
        mini = min(mini, 1.0 * sum[i + 1 - L] - (i + 1 - L) * x);
    }
    return false;
}
void solve(){
    double l = 1.0 * sum[n] / n, r = 1.0 * maxi;
    for(int i = 0; i < 60; ++i){
        double mid = (l + r) / 2;
        if(judge(mid)) l = mid;
        else r = mid;
    }
    printf("%d\n", (int)(1000 * l));
}
int main(){
    init();
    solve();
    return 0;
}