poj 1064 Cable master - Titanium - 博客园

Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it. 
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible. 
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled. 
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.

题意：给出n条线段，以米的单位给出，小数点后两位（精确到厘米），要你对这些线段裁剪，裁剪出m条等长的线段，并且让这些线段尽可能长另外线段的长度不能小于1厘米，如果筹不够m条，输出0.00
做法就是二分答案，但是二分的区间有讲究

这题可以用浮点数的二分来写，但是基于题目的意思，完全可以转化为整数

因为最后长度不能小于1厘米，而一开始给出的线段也是精确到厘米的，而答案也是要求精确到厘米的，那么为什么我们不一开始就把所有的数据都改成用厘米来表示呢？然后直接用整数来二分就可以避免掉所有精度的问题。所以一开始的二分区间就是[1,max{len[i]}] , 不要从0开始，完全没有比较，因为答案最小要为1

我们二分答案，得到一个长度l，然后用所有线段去除l，看能裁剪出多少条，然后统计条数的总和count

然后就分类

count < m，说明这个长度l太长，筹不够m条，所以要缩点长度l，去左半区间二分

count = m，说明是一个合法的答案，记录，但是这样就可以了吗?可以跳出了吗？不是的，因为要找最大值，所以不能跳出，继续到右半区间二分

count > m , 这是不是一个合法的答案？一开始没想清楚，认为不是合法的答案，其实是的！另外要到右半区间继续二分找一个更大的值

int main()
{
    int n,m;
    double len;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int Max = 0;
        for(int i=0; i<n; i++)
        {
            scanf("%lf",&len);
            a[i] = len * 100;
            Max = max(Max , a[i]);
        }
        int low = 1 , high = Max;
        int res = 0;
        while(low <= high)
        {
            int mid = (low + high) >> 1;
            int count = 0;
            for(int i=0; i<n; i++)
                count += a[i] / mid;

            if(count >= m)
                res = max(res , mid) , low = mid + 1;
            else
                high = mid - 1;
        }
        printf("%.2f\n",(double)res / 100.0);
    }
    return 0;
}

http://blog.csdn.net/wmn_wmn/article/details/7950797

1. double eps = 1e-5;  
2. const int N = 10010;  
3. double num[N];  
4. int main(){  
5.     //freopen("1.txt","r",stdin);  
6.     int n,k;  
7.     while(scanf("%d%d",&n,&k) != EOF){  
8.        double maxvalue = 0.0;  
9.        for(int i = 0; i < n; ++i){  
10.            scanf("%lf",&num[i]);  
11.            if(maxvalue < num[i])  
12.                maxvalue = num[i];  
13.        }  
14.        double lp = 0.00,rp = maxvalue,ans = 0.0;  
15.        while(rp - lp > eps){  
16.           double mid = (rp + lp) / 2.0;  
17.           int sum = 0;  
18.           for(int i = 0; i < n; ++i){  
19.             int x = (num[i] / mid );  
20.             sum += x;  
21.           }  
22.           if(sum >= k){  
23.               ans = mid;  
24.               lp = mid;  
25.           }  
26.           else{  
27.               rp = mid;  
28.           }  
29.        }  
30.        rp = rp * 100;  
31.        int yy = rp;  
32.        printf("%.2lf\n",yy * 0.01);  
33.     }  
34.     return 0;  
35. }  

思路：二分枚举答案，注意精度控制。浮点数的二分和整数的二分还不太一样，需要注意一下。

Read full article from poj 1064 Cable master - Titanium - 博客园