贪心算法阿明焊钢管算法Java代码
时间: 2024-06-17 11:07:57 浏览: 15
贪心算法是一种常见的算法思想,它通过每一步选择局部最优解,最终得到全局最优解。阿明焊钢管问题是一个典型的贪心算法问题,其Java代码如下:
```java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[m];
for (int i = 0; i < m; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);//将钢管长度排序
int cnt = 0;//计数器
int i = 0, j = m - 1;//i从小到大,j从大到小
while (i <= j) {
if (arr[j] < n) {//如果最长的钢管都小于n,无法满足要求
System.out.println(-1);
return;
}
cnt++;//选取了一根钢管
int k = n - arr[i];//剩余需要长度
while (j > i && arr[j - 1] >= k) {//寻找满足剩余长度的最长钢管
j--;
}
if (arr[j] >= k) {
j--;//选择该钢管
}
i++;//继续选取下一根
}
System.out.println(cnt);
}
}
```