Cable master POJ - 1064 (二分 精度问题)

题意: 有N条绳子, 长度分别为L, 如果从他们中切出K条长度相同的绳子的话, 求最长的长度, 报留小数点后两位(不作四舍五入)

题解: 这道题是白书上的一道经典二分问题, 但考的远远不止二分知识, 我们先来说说二分的问题
对于一个问题, 如果我们可以找到单调的序列, 以及明确的判定条件并能确定大致的范围, 就一定可以使用二分来优化
二分模板:

	int bSearch(int tar, int l, int r)
	{
	    while(l < r){
	        int mid = (l+r)/2;
	        if(check(mid)) l = mid;
	        else r = mid;
	    }
	    return l;
	}

这里的check函数我们定义为, 是否可以得到k条长度为x的绳子
代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 1e4+10;
const LL inf = 1e5+10;
const double eps = 1e-6;

int n, k;
double a[maxn];
bool check(double x)
{ //是否可以得到k条长度为x的绳子
    int sum = 0;
    for(int i = 1; i <= n; i++)
        sum += (int)(a[i]/x); //细节, 记得加括号
    return sum>=k;
}
int main()
{
    while(cin >> n >> k){
        double l = 0, r = 0;
        for(int i = 1; i <= n; i++)
            cin >> a[i], r = max(r, a[i]);

        while(r-l > eps){
            double mid = (l+r)/2;
            //cout << mid << endl;
            if(check(mid)) l = mid;
            else r = mid;
        }
        printf("%.2f\n",floor(r*100)/100); //细节, 保留小数点而不是四舍五入
    }
	return 0;
}

然而这题考的远远不止简单二分, 更头疼的精度问题
代码中注释了两处一定要小心注意
另外对于浮点的输入输出, G++和C++是有着很大区别的

同时在G++里最好不要scanf和cin混着用…我就这样导致了TLE, 虽然不知道为啥…