【练习题】锯木头问题

锯木头问题

木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定的。当然,我们希望得到的小段越长越好,你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是 cm。原木的长度都是正整数,我们要求切割得到的小段木头的长度也是正整数。

【输入格式】第一行是两个正整数 N和K(1N<10000,1

【输出格式】输出能够切割得到的小段的最大长度。如果连 1 cm 长的小段都切不出来,输出“0”

暴力破解法（C语言）

#include
#include
int main() {int n, m,sum=0;scanf("%d%d", &n, &m);int* p = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++){scanf("%d", p + i);sum += p[i];}sum /= m;while (1) {int o = 0;for (int i = 0; i < n; i++){o += p[i] / sum;}if (o == m) {printf("%d", sum);break;}sum--;}free(p);	
}

二分法（C语言）

int cut(int*p,int v,int n) {int o = 0;for (int i = 0; i < n; i++){o += p[i] / v;}return o;
}
#include
#include
int main() {int n, m,sum=0;scanf("%d%d", &n, &m);int* p = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++){scanf("%d", p + i);sum += p[i];}sum /= m;for (int i = 1,j=sum; i <= j; i++){int v = (i + j) / 2;if (cut(p,v,n) == m&&cut(p,v+1,n)!=m) {printf("%d", v);break;}else if(cut(p, v, n) <m){j = v - 1;}else {i = v+1;}}free(p);	
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！