首页 > 代码库 > OpenJudge 2774 木材加工
OpenJudge 2774 木材加工
1.链接:
http://bailian.openjudge.cn/practice/2774/
2.题目:
- 总Time Limit:
- 1000ms
- Memory Limit:
- 65536kB
- Description
- 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数,我们要求切割得到的小段木头的长度也要求是正整数。- Input
第一行是两个正整数N和K(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000),N是原木的数目,K是需要得到的小段的数目。
接下来的N行,每行有一个1到10000之间的正整数,表示一根原木的长度。
- Output
- 输出能够切割得到的小段的最大长度。如果连1厘米长的小段都切不出来,输出"0"。
- Sample Input
3 7232124456- Sample Output
114- Source
- NOIP 2004
3.思路:
利用二分查找减少计算的次数
4.代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int main() 8 { 9 //freopen("C://input.txt","r",stdin);10 11 int i;12 13 int n,k;14 cin >> n >> k;15 16 int sum; //sum of stick length17 18 int *arr_len = new int[n];19 memset(arr_len , 0, sizeof(int) * n);20 21 sum = 0;22 for(i = 0; i < n; ++i)23 {24 cin >> arr_len[i];25 sum += arr_len[i];26 }27 28 int max_len = sum / k;29 int min_len = 1;30 int mid_len;31 32 int count_k;33 int max = 0;34 35 while(min_len <= max_len)36 {37 mid_len = (max_len + min_len) / 2;38 39 count_k = 0;40 for(i = 0; i < n; ++i)41 {42 count_k += (arr_len[i] / mid_len);43 }44 45 if(count_k >= k)46 {47 if(max < mid_len) max = mid_len;48 min_len = mid_len + 1;49 }50 else51 {52 max_len = mid_len - 1;53 }54 }55 56 cout << max << endl;57 58 delete [] arr_len;59 60 return 0;61 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。