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;
}
上一篇: CCF CSP 20180302 C++
下一篇: 嵌入式开发基础掌握