Best Cow Fences(PO2018)

青旅半醒 2021-12-22 15:33 165阅读 0赞

农夫约翰的农场由一长排N (1 <= N <= 100,000)块地组成。每个土地包含一定数量的奶牛，1 <= ncows <= 2000。想要在一组相邻的牧场周围建一个篱笆，以便最大化该组内每块牧场的平均奶牛数量。每组必须包含至少F (1 <= F <= N)土地，其中F作为输入。在给定约束条件下，计算使平均值最大化的栅栏位置。

输入输出格式：

输入：第一行输入N，F，接下来每一行输入每个土地的奶牛数。

输出：一个整数，它是最大平均值的1000倍。不执行四舍五入，只打印1000\*ncows/nfields的整数。

输入样例：  
10 6  
6  
4  
2  
10  
3  
8  
5  
9  
4  
1

输出样例：  
6500

大意：给定正整数数列A，求一个平均数最大的、长度不小于L的子段。

分析：

判定：是否存在一个长度不小于L,平均数不小于二分的值

前缀和求解一个字段长度不小于L，和最大

题解： 这题容易TLE,注意精度选择和区间缩小

#include<iostream>
    using namespace std;
    
    double a[100001],b[1000001],sum[100001];
    
    int main(){
        int N,L;
        cin>>N>>L;
        double l = 1e9,r = 0;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            l = min(l,a[i]);
            r = max(r,a[i]);  
        }
    
        double eps = 1e-4;
        
    
        while(r-l>eps){
            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 ans = -1e10;
            double min_val = 1e10;
            for(int i=L;i<=N;i++){
                min_val = min(min_val,sum[i-L]);   
                ans = max(ans,sum[i] - min_val);
            }
    
            if(ans>=0) l = mid;
            else r = mid;
        }
        cout<< int(r*1000)<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/wendiudiu/p/10765874.html