二分

二分查找

二分查找
二分查找十分的高效，因为每次查找都会淘汰当前的一半数据，但是查找的元素必须是有序的；

基本代码模板

quick_search(int a[],int n,int m)//a[]为需要查询的数组，n为数组长度，m为待查元素 
{
	int start = 0;
	int end = n-1;
	int mod;
	while(start<=end)
	{
		mod=(start+end)/2;
		if(a[mod]>m)
			end=mod-1;
		else if(a[mod]<m)
			start=mod+1;
		else
			return 1;//查询到 
	 } 
	
	return 0;//未查询到 
}

题目Trailing Zeroes (III)
给出m,求最小n,n!末尾有m个0

分析：求n!中0的个即求n！中5的个数
二分查询5的个数即可

#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int abd(int m)//计算m！中5的个数
{
	int a=0;
	while(m>0)
	{
		a+=m/5;
		m/=5;
	}
	return a;
}
int abc(int m)
{
	int start=5;
	int end=5e8；
	int mod;
	while(start<=end)
	{
		mod=(start/5+end/5)/2*5;
		if(abd(mod)>m)
			end=mod-5;
		else if(abd(mod)<m)
			start=mod+5;
		else
			return mod;
	}
	return -1;
}
int main()
{
	int n;
	int time=0;
	scanf("%d",&n);
	while(n--)
	{
		time++;
		int m;
		scanf("%d",&m);
		if(abc(m)==-1)
			printf("Case %d: impossible\n",time);
		else
			printf("Case %d: %d\n",time,abc(m));
	}
	return 0;
}

二分逼近

hdu1969 pie

#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const double l=1e-6;
double pi=acos(-1.0);
int abd(double a[],int m,double mod)
{
	int sam=0;
	for(int i=0;i<m;i++)
	{
		sam+=(int)(a[i]/mod);
	}
	return sam;
}
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		double a[10005];
		int m,f;
		double sam=0;
		scanf("%d%d",&m,&f);
		for(int i=0;i<m;i++)
		{
			double x;
			scanf("%lf",&x);
			a[i]=x*x;
			sam+=a[i];
		}
		double start=0;
		double end=sam/(f+1);
		double mod;
		while(end-start>l)
		{
			mod=(start+end)/2;
			if(abd(a,m,mod)<f+1)
				end=mod-l;
			else
				start=mod+l;
		}
		printf("%0.4lf\n",mod*pi);
	}
	return 0;
}

poj 2456 Aggressive cows