---
# System prepended metadata

title: 1891. Cutting Ribbons
tags: [Leetcode, Binary Search, Medium]

---

# 1891. Cutting Ribbons
###### tags: `Leetcode` `Medium` `Binary Search`
Link: https://leetcode.com/problems/cutting-ribbons/
## 思路
Binary Search那边纠缠了很久
总结
- 如果while里面用<= if和else的判断里面就一个是mid+1一个是mid-1
因为最极限的条件是 start==end 如果不这样写就会一直卡在start=end
- 如果while里面用< if和else里面就一个是```l=mid+1``` 一个是```r=mid```,因为极限的条件是start==end-1，这时候mid会等于start

要注意的地方：
- sum一定要用long存
- checkLength()==k，还是要继续往右挪，继续找
## Code
```java=
class Solution {
    public int maxLength(int[] ribbons, int k) {
        int start = 1;
        int end = 1;
        long sum = 0;
        for(int i = 0;i < ribbons.length;i++){
            sum += ribbons[i];
            end = Math.max(end, ribbons[i]);
        }
        if(sum < k) return 0;
        end += 1;
        while(start<end){
            int mid = start+(end-start)/2;
            if(checkLength(ribbons, mid)>=k){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        return start-1;
    }
    public int checkLength(int[] ribbons, int len){
        int cnt = 0;
        for(int i = 0;i < ribbons.length;i++){
            cnt += ribbons[i]/len;
        }
        return cnt;
    }
}
```