算法竞赛--二分(二)

二分法扩展

1.计算根号2的近似值

思路:令浮点型low和high的初值分别为1和2，然后根据low和high的中点mid处ff(mid)的值与2的大小来选择子区间进行逼近。

如果ff(mid)>2,则应当在[left,mid]的范围内继续逼近，否则则在[mid,right]的范围内继续逼近。

参考代码如下:

#include<stdio.h>
const double min=1e-5;
double ff(double x)
{
	return x*x;
}
int main()
{
	double low=1,high=2,mid;
	while(high-low>min)
	{
		mid=(low+high)/2.0;
		if(ff(mid)>2)
			high=mid;
		else
			low=mid;
	}
	printf("%.5f",mid);
	return 0;
}

2.装水问题

有一个侧面看去是半圆的储水装置，该半圆的半径为R,要求往里面装入高度为h的水,有使其在侧面看去的面积与半圆面积的比例恰好为r，如下图所示。现在给定R和r，求高度h。

思路:随着水面升高，面积比例r一定是增大的，在[0,R]之间进行二分，求出比例rr,如果rr>r,在[0,rr]的范围内，否则在[rr,R]范围内，直至rr和r的差值小于1e-5；

参考代码如下:

#include <stdio.h>
#include <math.h>
const double PI=acos(-1);
const double min=1e-5;
double fr(double R,double h)		//计算比例rr
{
	double a=2*acos((R-h)/R);
	double l=sqrt(R*R-(R-h)*(R-h));
	double s1=R*R*a/2-l*(R-h);
	double s2=R*R*PI/2;
	return s1/s2;
}
int main()
{
	double R,r;
	scanf("%lf%lf",&R,&r);
	double low=0,high=R,mid;
	while(high-low>min)			//二分法逼近
	{
		mid=(low+high)/2;
		if(fr(R,mid)>r)
			high=mid;
		else
			low=mid;
	}
	printf("%.4f",mid);
	return 0;
}

3.木棒切割问题

给出N根木棒长度已知但不一定相等， 现在希望通过切割得到长度相等的K根木棒，求长度相等的K根木棒最长是多少？

如：给3根木棒，长度为10， 24， 15，要切割得到7根长度相等的木棒， 则7根木棒的长度最长为6，其组合为16+46+2*6。

暴力解法:

#include<stdio.h>
int a[10010];
int main()
{
	int n,K;
	scanf("%d%d",&n,&K);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	int len=1,num;
	do
	{
		num=0;
		for(int i=0;i<n;i++)
			num+=a[i]%len;
		len++;
	}while(num!=K);
	printf("%d",len-1);
	return 0;
}

二分解法:

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[10010];
int main()
{
	int n,K;
	scanf("%d%d",&n,&K);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	sort(a,a+n);	
	int low=0,high=a[n-1],mid;
	while(low+1<high)		//长度进行逼近
	{
		int num=0;
		mid=(low+high)/2;
		for(int i=0;i<n;i++)
			num+=a[i]/mid;
		if(num<K)
			high=mid;
		else
			low=mid;
	}
	printf("%d",low);
	return 0;
}