剪绳子

原题链接

思路：

• 二分法
  • 绳子最长为 1e9
  • 考虑二分：
    • 若当前绳长满足要求，则说明还有可能取更长的绳长；
    • 若当前绳长不满足要求，则说明当前绳长不可能是最终答案；
    • 由于绳子长度需保留两位小数，当二分边界差值不超过 eps = 1e-4 时即可结束。
  • 利用数组 a[N] 存储各段绳子的长度，对于第 i 根绳子，可截取的段数为 int(a[i] / mid)。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 1e6 + 3;
const double eps = 1e-4;
int a[N];

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

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    double l = 0, r = 1e9;
    while (l < r) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
        if (r - l < eps) break;
    }
    printf("%.2lf\n", l);
}

int main() {
    solve();
    return 0;
}