【算法】二分答案

二分答案转化为判定

这对于我来说好像是一种特别玄学的方法。

 

一个宏观的最优化问题也可抽象为函数,定义域为可行方案,对可行方案评估得到的值就是函数的值域,最优解就是评估值最优的方案。

假设最优解的评分为S,显然对于所有>S的值,都不存在一个合法的方案来达到该评分,否则就不和假设;而对于所有<S的值,一定存在一个合法的方案来达到或超过该值,因为最优解就满足这个条件。这样值域就有一个特殊的单调性,在S的一侧合法,另一侧不合法。

借助二分,我们可以把求解最优解的问题转化为给定一个mid,判断是否存在一个可行方案评分达到mid的问题。

举个例子:

N本书排成一行,已知第i本书的厚度为A_{i}

把它们分成连续的M组,使T最小化,T表示厚度之和最大一组的厚度。

这里有最大值最小,这是答案具有单调性,可用二分转化判定的最常见,典型特征之一。

我们以划分为M组的方案为定义域,T为值域,且T越小越优。

假设最终答案为S,因为S的最优性,如果每组厚度都<S,那么就不存在可行解;如果每组厚度可以>S,那么一定存在一种方案使得组数不超过M,最优解就在可行解的分界点上。

bool div(int size){
	int group = 1,rest = size;
	for(int i = 1;i <= n;i++){
		if(rest >= a[i]){
			rest -= a[i];
		}else{
			group++;
			rest = size - a[i];
		}
	}
	return group <= m;
}

int main(){
	int l = 0,r = sumOfA;
	while(l < r){
		int mid = (l + r) / 2;
		if(div(mid)){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	printf("%d",l);
	
	return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注