二分总结一 二分法试解 POJ1064

http://poj.org/problem?id=1064
二分法不止可以用于查找  这篇博客以及接下来几篇会举例说明
本篇博客讲一种二分法的用途
题目很简单，就是n条绳子，要求分为k段，求每段最大的长度
记录最长的绳子
然后二分绳长，依次试解
同时还学到了一个小技巧，

小数向下保留位数的方法  
如向下保留两位
floor(mmax*100)/100

#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAXN 10003

double a[MAXN];
int k,n;

int C(double x)
{
    int i,tot=0;

    for(i=0;i<n;i++)
    {
        tot+=(int)(a[i]/x);
    }
    //if(tot>=k)return 1;
    //else return 0;
    return tot>=k;
}

int main()
{
    int i;
    double mmax,d,u;

    while(scanf("%d%d",&n,&k)!=EOF)
    {
        mmax=-1;
        for(i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
            mmax=max(mmax,a[i]);
        }

        d=0;u=mmax;
        for(i=0;i<100;i++)
        {

            if(C(mmax))d=mmax;
            else u=mmax;
            mmax=(d+u)/2;
        }

        printf("%.2lf\n",floor(u*100)/100);
        /*这个地方有个陷阱。2f是四舍五入的，所以floor(mmax*100)/100保证的只是舍而不入，比如你算出来的最大长度*/
    }

    return 0;
}

二分总结一 二分法试解 POJ1064

原文：http://blog.csdn.net/u011026968/article/details/19653477