题目链接

Cable master POJ - 1064

思路

$$ 假设一个可行接然后验证 $$

时间复杂度

$$ O(Nlog(max(a_i))) $$

代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1e4 + 10;
int n, m;
long long a[MAXN];

bool check(int mid) {
    if (mid == 0) {
        return true;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += a[i] / mid;
    }
    return cnt >= m;
}

int main() {
    scanf("%d%d", &n, &m);// don't forget &
    long long l = 0, r = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        float x;
        scanf("%f", &x);// don't forget &
        x *= 100;
        a[i] = x;
        r = max(r, a[i]);
    }
    while (l <= r) {
        long long mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    printf("%.2f", 1.0 * ans / 100);
    return 0;
}