ACM_算法题：左老师锯木头

左老师锯木头

时间限制：1s 内存限制：128MB

题目描述

木材厂有 n 根原木，现在左老师想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 l 的最大值。

木头长度的单位是cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 11 和 21，要求切割成等长的 6段，很明显能切割出来的小段木头长度最长为5。

输入格式

第一行是两个正整数 n,k，分别表示原木的数量，需要得到的小段的数量。

接下来 n 行，每行一个正整数 Li 表示一根原木的长度。

输出格式

仅一行，即 l 的最大值。

如果连 1cm 长的小段都切不出来，输出 0。

样例输入

3 7

232

124

456

样例输出

114

提示/说明

对于 100%100% 的数据，有 1≤n≤10

5

，1≤k≤10

8

，1≤Li≤10

8

(i∈[1,n])。

其中，woods数组存储了每根原木的长度，maxLen表示原木中的最大长度。left和right分别表示答案的范围，初始时left为1，right为maxLen。在二分答案的过程中，我们每次取mid为(left+right+1)/2，然后计算当前答案下能够得到的小段木头的数量cnt。如果cnt大于等于k，则说明当前答案合法，我们尝试缩小答案的范围；否则说明当前答案不合法，我们尝试扩大答案的范围。最终，left就是我们要求的最大值。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int k = scanner.nextInt();//这两行代码读取了输入的n和k。int[] woods = new int[n];int maxLen = 0;for (int i = 0; i < n; i++) {woods[i] = scanner.nextInt();maxLen = Math.max(maxLen, woods[i]);}//这几行代码读取了每根原木的长度，并计算出了原木中的最大长度。int left = 1;int right = maxLen;//这两行代码初始化了答案的范围，初始时left为1，right为maxLen。while (left < right) {int mid = (left + right + 1) / 2;int cnt = 0;for (int i = 0; i < n; i++) {cnt += woods[i] / mid;}if (cnt >= k) {left = mid;} else {right = mid - 1;}}//这几行代码实现了二分答案的过程。在每次循环中，我们取mid为(left+right+1)/2，然后计算当前答案下能够得到的小段木头的数量cnt。如果cnt大于等于k，则说明当前答案合法，我们尝试缩小答案的范围；否则说明当前答案不合法。System.out.println(left);}
}

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