欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2018 Best Cow Fences

程序员文章站 2022-06-09 09:42:12
...

是一道经典的二分题(可我一开始并不会做  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