有 n 条绳子,每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割,但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段,求绳段的最大长度是多少。 输入:第一行是一个不超过100的正整数 n ,第二行是 n 个不超过106的正整数,表示每条绳子的长度,第三行是一个不超过108的正整数 m 。 输出:绳段的最大长度,若无法切割,输出 Failed .
时间: 2023-05-20 17:04:25 浏览: 91
这是一道比较经典的二分答案问题,我们可以先对绳子长度进行排序,然后二分答案,判断当前答案是否可行。具体实现可以参考以下代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
int a[MAXN];
bool check(int x) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += a[i] / x;
if (cnt >= m) return true;
}
return false;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> m;
sort(a + 1, a + n + 1);
int l = 1, r = a[n], ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ans == 0) {
cout << "Failed" << endl;
} else {
cout << ans << endl;
}
return 0;
}
对于每个可能的答案 x,我们遍历所有绳子,计算可以切出多少段长度为 x 的绳子。如果总段数大于等于 m,则说明当前答案可行,否则不可行。最后输出最大可行的答案即可。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)