长m的绳子,每天用一半,n天后的长度,c++
时间: 2023-05-31 07:01:35 浏览: 69
每天使用一半,则n天后长度为:
$\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times ... \times \frac{1}{2} \times m$
共有n个$\frac{1}{2}$相乘,所以可以表示为:
$\frac{1}{2^n} \times m$
即长度为:
$c = \frac{1}{2^n} \times m$
相关问题
有n根绳子,第i根绳子长度为li,现在需要m根等长的绳子,你可以对n根绳子进行任意裁剪(不能拼接),请你帮忙计算出这m根绳子最长的长度是多少。
将n根绳子中最长的那根绳子记为max_len,最短的那根绳子记为min_len。由于要将n根绳子裁剪成m根等长的绳子,所以最长的绳子长度不能超过max_len/m,最短的绳子长度不能小于min_len/m。
因此,我们可以使用二分查找来确定最长的绳子长度。假设当前二分的区间为[l, r],则取mid=(l+r)/2作为绳子长度进行判断。遍历n根绳子,将每根绳子长度除以mid,得到的商之和记为cnt。如果cnt>=m,则说明当前绳子长度可以满足要求,将区间左端点更新为mid+1;否则,说明当前绳子长度不足以满足要求,将区间右端点更新为mid-1。
最终,当l>r时,区间右端点即为所求的最长绳子长度。
用C语言有n条绳子,每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割,但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段,求绳段的最大长度是多少。
这是一个二分答案的问题。
首先,我们可以先求出所有绳子长度的最小值min和最大值max,因为绳段的长度不可能小于最小值,也不可能大于最大值。
然后,我们可以使用二分答案的思想,假设绳段的长度为mid,然后遍历所有绳子,计算出可以从这些绳子中切割出多少条长度为mid的绳段。如果数量大于等于m,则说明mid长度的绳段可行,我们把左边界更新为mid+1;否则说明mid长度的绳段不可行,我们把右边界更新为mid-1。最终,左边界就是最大长度。
代码如下:
```c
int check(int n, int m, int a[], int x) {
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += a[i] / x;
}
return cnt >= m;
}
int cut_rope(int n, int m, int a[]) {
int l = 1, r = 1e9;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(n, m, a, mid)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return r;
}
```
其中,check函数用于判断是否可以从所有绳子中切割出m条长度为x的绳段。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)