ACM_二分（POJ1064）

1.二分法求解問題的這種思想其實十分的普遍。回憶一下我們在求一個方程的近似根的時候其實使用的就是二分的辦法，當然這種求近似根的方法是有一定局限的，因為這樣無法求不變号的零點，也就說哪種曲線剛剛好與坐标軸相切的零點我們通過普通的二分是無法求得的。但是，二分求近似根這種方法展現出來的二分思想其實是可以被用來解決很多的問題。

2.二分查找。如果我們在一個有序的數組裡查找不大于某個數最大的下标，其實我們就可以通過二分來做，具體的代碼在這裡就不寫了，思想和求根一樣，不斷的二分查找區間，直到找到為止。這樣其實我們把複雜度下降到logn。

#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<math.h>
#pragma warning(disable:4996)
using namespace std;
const int maxn = 1e4 + 10;
int N, K;
double len[maxn];
#define INF 2e5+10;
bool OK(double c)
{
    int num = 0;
    for (int i = 0; i < N; i++)
    {
        num += (int)(len[i] / c);
    }
    return num >= K;
}
void solve()
{
    double l = 0;
    double r = INF;
    for (int i = 0; i < 100; i++)
    {
        double mid = (l + r) / 2;
        if (OK(mid))l = mid;
        else r = mid;
    }
    printf("%0.2f\n", floor(r * 100) / 100);
}
int main()
{
    while (cin >> N >> K)
    {
        for (int i(0); i < N; i++)
            scanf("%lf", len + i);
        solve();
    }
    return 0;
}