二分算法2-二分答案

//二分算法2——二分答案

//解法一：暴力算法
// 枚举所有的切割长度x
// 求出在x的情况下 ，能够切出来多少段

//解法二：利用二分来优化
// x表示：切割出来的小段的长度
// cnt表示：在x的基础下，最多能切出来多少段
// k表示：最终要切割的段数

include

using namespace std;
typedef long long LL; // 关键：木材长度/段数可能很大，用LL避免溢出

const int N = 1e5 + 10; // 最多1e5根木材
LL n, k; // n：木材数量，k：需要的最少段数
LL a[N]; // 存储每根木材的长度

// 核心函数：给定小段长度x，计算能切割出的总段数
LL calc(LL x){
LL cnt = 0; // 总段数
for(int i = 1; i <= n; i++){
cnt += a[i] / x; // 每根木材a[i]能切出a[i]/x段长度为x的小段（向下取整）
}
return cnt;
}

int main(){
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];

// 二分答案的核心逻辑
LL left = 0, right = 1e8; // 答案的范围：最小0，最大设为1e8（足够覆盖题目范围）
while(left < right){ // 收敛到唯一的最大xLL mid = (left + right + 1) / 2; // 向上取整（关键！）if(calc(mid) >= k){ // 总段数≥k，说明x可以更大，尝试往右找left = mid;} else { // 总段数<k，说明x太大了，需要往左找right = mid - 1;}
}
cout << left << endl; // 循环结束时left=right，就是最大的x
return 0;

}