C++程序算法题
文章正文
发布时间:2024-07-09 17:11
题目问题
木材厂有一些本木,如今想把那些木头切割成一些长度雷同的小段木头,须要获得的小段的数目是给定了。虽然,咱们欲望获得的小段越长越好,你的任务是计较能够获得的小段木头的最大长度。
木头长度的单位是厘米。本木的长度都是正整数,咱们要求切割获得的小段木头的长度也要求是正整数。
Input
第一止是两个正整数N和K(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000),N是本木的数目,K是须要获得的小段的数目。
接下来的N止,每止有一个1到10000之间的正整数,默示一根本木的长度。
Output
输出能够切割获得的小段的最大长度。假如连1厘米长的小段都切不出来,输出"0"。
Sample Input
3 7
232
124
456
Sample Output
114
思路:
刚初步用的暴力搜寻,结果光阳超时。最后冤家讲述我用二分法。详细思想二分法的思想读者原人查找量料浏览。
1、右值为0,左值为数组最大值+V (V可以与任何值,正常与1-100便可)
2、最后输出最大切割长度为左值-1
代码:
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int N,K;
cin>>N>>K;
int wood[10000];
for(int i=0;i<N;i++){
cin>>wood[i];
}
int lef = 0;
int maV_cut = 0;
// 升序
sort(wood,wood+N);
int rig = wood[N-1]+1;
// 二分法
while(lef<rig){
int sum = 0;
int mid = (rig+lef)/2;
if(mid==0){
break;
}
for(int i=0;i<N;i++){
sum += wood[i]/mid;
}
if(sum>=K){
lef = mid+1;
}else{
rig = mid;
}
}
cout<<rig-1;
}
运止结果: