POJ 2018 Best Cow Fences

本文主要是介绍POJ 2018 Best Cow Fences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

是一道经典的二分题（可我一开始并不会做  http://poj.org/problem?id=2018

从题意来看很快就能分析出这是一道二分题，而且应该是二分答案，但难点就是如何在O（n）的复杂度内判断它是否满足条件，具体的解释我已经注释上了，还是不太清楚的，可以结合画图来看。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+5;
int N,F;
int f[maxn];
double tmp[maxn],ssum[maxn];
bool cmp(double mid){//核心 for(int i=1;i<=N;++i){tmp[i]=(double)f[i]-mid;//每个剪掉平均值，即去找有没有一段和>=0且长度>=F ssum[i]=ssum[i-1]+tmp[i];//前缀和 }double ans=-1,mmin=1e9+5;	for(int i=F;i<=N;++i){ //以i为右端点，可取长度>=F的，即左端点可以在1~i-F+1里取 //不断跟新小于平均值的那一部分(前缀和越小，小于0，说明他达不到mid平均值mmin=min(mmin,ssum[i-F]); //只会拉低平均值 ans=max(ans,ssum[i]-mmin);//剪掉拉低平均值的，即得到以i为右端点最大的平均值 }if(ans>=0)	return 1;else	return 0;
}
int main() {scanf("%d%d",&N,&F);int mmax=-1,mmin=1e9+5;for(int i=1;i<=N;++i){scanf("%d",f+i);mmax=max(mmax,f[i]);mmin=min(mmin,f[i]);}double le=double(mmin),ri=double(mmax);while(ri-le>(double)1e-6){double mid=(le+ri)/2;if(cmp(mid))le=mid;else	ri=mid;}cout<<(int)(ri*1000)<<endl;return 0; 
}

 

这篇关于POJ 2018 Best Cow Fences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---