智能书签

题目问题 木材厂有一些本木，如今想把那些木头切割成一些长度雷同的小段木头，须要获得的小段的数目是给定了。虽然，咱们欲望获得的小段越长越好，你的任务是计较能够获得的小段木头的最大长度。 木头长度的单位是厘米。本木的长度都是正整数，咱们要求切割获得的小段木头的长度也要求是正整数。 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; } 运止结果：