USACO Sabotage, 2014 Mar 破坏阴谋(二分+贪心)

一开始看完这题就有个想法：

只要把大于整个序列平均数的最大连续序列就是最优？

那把整个序列都减掉平均数在做最大连续字序列和且记录长度？

仔细思考一下并不太对；

当子序列最大但长度较大也许也比不上删去一个超过平均数许多的机器；

盲目的贪心是错的；但找对方向问题就解决了；

我们可以发现若删除机器后平均值越小；超过这平均值的可删除的机器就越多；

满足了单调性；就可以二分了；

至于check（）就是基于上面的贪心；也是预处理后做最大连续字序列和做判断；

T（nlogn）

#include<cstdio>

#include<cstring>

using namespace std;

double mid,a[100010],maxx,ans,s,l,r;

int n,i,j,k;

bool check(double x)

{

	int num=0;double sum=0;

	for(i=2;i<n;++i)

	{

		if(sum+a[i]>0)

		sum+=a[i],num++;

		else sum=a[i],num=1;

		if(sum<a[i])sum=a[i],num=1;

		if((ans-1.0*sum-num*x)/(n-num)<=mid)return true;

	}

	return false;

}

int main()

{

//	freopen("xx.in","r",stdin);

	scanf("%d",&n);

	for(i=1;i<=n;++i)

	{

		scanf("%lf",&a[i]);

		ans+=a[i];

	}

	r=1e9;l=1;

	while(l+1e-6<r)

	{

		mid=(l+r)/2;

		for(i=2;i<n;++i)a[i]-=mid;

		if(check(mid))r=mid;

		else l=mid;

		for(i=2;i<n;++i)a[i]+=mid;

	}

	printf("%.3lf",r+5e-6);

}

巴特西

USACO Sabotage, 2014 Mar 破坏阴谋(二分+贪心)

最新文章

热门文章