X010 切绳子
大约 2 分钟
X010 切绳子
【算法】 二分答案(浮点二分)
【C++】 浮点二分、double、floor
【难度】 普及/提高−
一、题目简述
有 条绳子,第 条长度为 。需要从中切出 条长度相等的绳子(不能拼接),求能切出的最大长度。结果保留 2 位小数,多余位数直接舍去(不四舍五入)。
数据范围:,,。
二、解题思路
1. 为什么能用二分
单调性:切出的绳子长度 越大,能切出的段数越少。如果长度为 时能切出 ≥ 段,那么任何小于 的长度也能满足条件。反之,如果 不能满足,任何大于 的长度也不能满足。
判定结果呈现出"前半段可行、后半段不可行"的单调模式,符合二分的条件。
2. check 函数设计
check(mid):对于每条绳子 ,它能切出 段长度为 的绳子。累加所有绳子切出的段数,判断是否 ≥ 。
3. 浮点二分的细节
本题是浮点二分,答案保留 2 位小数。精度的处理有两个要点:
二分次数:不设定精度阈值 r - l > eps(容易死循环),而是固定迭代 60~80 次。每次区间减半,80 次后误差远小于 ,足够精确。
直接舍去:printf("%.2f") 默认会四舍五入,不符合题意。使用 floor(ans * 100) / 100 实现直接舍去。
4. 手动模拟
假设 3 条绳子长度 [8.02, 7.43, 4.57],需要切出 11 段:
| 尝试长度 | 8.02 段数 | 7.43 段数 | 4.57 段数 | 总段数 | 判定 |
|---|---|---|---|---|---|
| 2.00 | 4 | 3 | 2 | 9 | ❌ 不够 |
| 1.00 | 8 | 7 | 4 | 19 | ✅ 可行 |
| 1.50 | 5 | 4 | 3 | 12 | ✅ 可行 |
| 1.75 | 4 | 4 | 2 | 10 | ❌ 不够 |
| 1.62 | 4 | 4 | 2 | 10 | ❌ 不够 |
| 1.56 | 5 | 4 | 2 | 11 | ✅ 可行 |
答案约为 1.56(舍去后为 1.56)。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
double L[N];
int n, K;
bool check(double mid) {
int cnt = 0;
for (int i = 1; i <= n; i++)
cnt += (int)(L[i] / mid);
return cnt >= K;
}
int main() {
cin >> n >> K;
for (int i = 1; i <= n; i++) cin >> L[i];
double l = 0, r = 1e9, ans = 0;
for (int t = 0; t < 80; t++) {
double mid = (l + r) / 2;
if (check(mid)) { ans = mid; l = mid; }
else r = mid;
}
printf("%.2f\n", floor(ans * 100) / 100);
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是二分迭代次数(固定 80 次)。每次
check遍历 条绳子,总体 。 - 空间复杂度:,存储绳子长度数组。
