Poj2018 Best Cow Fences

传送门

  题目大意就是给定一个长度为 n 的正整数序列 A ,求一个平均数最大的,长度不小于 L 的子序列。

思路:

  二分答案。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
#define lck_max(a,b) ((a)>(b)?(a):(b))
#define lck_min(a,b) ((a)<(b)?(a):(b))
typedef long long LL;
const int maxn=1e7+;
LL N,L;
double a[maxn],b[maxn],sum[maxn];
inline double resd() {double ls;scanf("%lf",&ls);return ls;}
inline LL read()
{
LL kr=,xs=;char ls;
ls=getchar();
while(!isdigit(ls))
{
if(!(ls^))
kr=-;
ls=getchar();
}
while(isdigit(ls))
{
xs=(xs<<)+(xs<<)+(ls^);
ls=getchar();
}
return xs*kr;
}
int main()
{
N=read();L=read();
for(LL i=;i<=N;i++) a[i]=resd();
double l=-1e6,r=1e6,eps=1e-;
while(r-l>eps)
{
double mid=(l+r)/;
for(LL i=;i<=N;i++) b[i]=a[i]-mid;
for(LL i=;i<=N;i++) sum[i]=sum[i-]+b[i];
double maxx=-1e10,minn=1e10;
for(LL i=L;i<=N;i++)
minn=lck_min(minn,sum[i-L]),maxx=lck_max(maxx,sum[i]-minn);
if(maxx>=) l=mid;
else r=mid;
}
printf("%lld\n",LL(r*));
return ;
}
上一篇:Android 实现FlowLayout流式布局(热门标签)


下一篇:10款基于jquery实现的超酷动画源码