[Acwing] 102. Zuijia牛围栏 二分答案

前言

加把劲 ! 传送门 :

思路

这道题如果是普通做法,显然就是一个个枚举出来,必然是不可能这么做的

所以我们可以用二分来优化查找过程 :

二分无非就是分为以下两种 :

• 二分答案
• 二分查找

二分查找是查找左右区间 : 对于这题来说显然不可能

而二分答案 , 我们发现有一个平均值可以做来二分

所以我们可以试着二分答案,但是二分答案最难的是在 c h e c k check check里面

那么我们怎么 c h e c k check check呢 ? 学过图论的朋友应该知道

对于这种求题,我们一般可以使用前缀和来求解 s u m [ i ] − m i d sum[i]-mid sum[i]−mid

因为这样子可以将问题转化为,是否有一段区间满足 s u m [ i ] − m i d > 0 sum[i]-mid>0 sum[i]−mid>0

所以当我们处理完前缀和之后,我们就可以使用,双指针来就，枚举区间

但是显然,比 F F F 大的区间也是可以取的,所以我们需要每次记录一个极小值

CODE

const int N  = 1e5+10;
const double eps = 1e-5;

double a[N];
double sum[N];

int n,m;

bool check(double x)
{
	for(int i=1;i>n>>m;
	double l = 1, r = 0 ;
	
	for(int i = 1;i>a[i];
		r =max(r,a[i]);
	}
	
	 while(r - l > eps)
	 {
		 double mid = (l+r)/2;
		 if(check(mid)) 
		 l = mid;
		 else
		r = mid;
	 }

	 cout