题目描述
使用火柴组成一个最大的数字, 规定:
可组成的数字 1 2 3 4 5 6 7 8 9
所需火柴数量 2 5 5 4 5 6 3 7 6
给定火柴总数m, 组成n位数字, 输出可以组成的最大值. 如果不能组成最大的数字, 输出0
题目要求组成最大值，可知所需火柴数量相同的数字中只需要最大的即可，所以真正需要的是：
所需数字：9 8 7 5 4 1
火柴数量：6 7 3 5 4 2
解题思路
采用贪心法从低位逐一确认最优解(数字最大)。
该位的最优解要满足剩下的火柴数量恰好足够n-i位使用(i为已确定的位数)。
那什么情况没有恰好满足剩下的n-i位使用呢？
- m < 2*n, n位火柴使用数量最小的数，火柴不够用。
- m > 7*n, n位火柴使用数量最大的数，火柴太多。
Code
import java.util.Scanner;
public class Main {
static String maxSum(int m, int n) {
final StringBuilder sb = new StringBuilder();
//二维数组，表示数字和火柴数量
int[][] a = new int[][]{{9, 8, 7, 5, 4, 1},{6, 7, 3, 5, 4, 2}};
// 从低位构建每一位
while (n > 0) {
int i = -1;
for (int j = 0; j < a[0].length; j++) {
//可构成每位最优解的条件
if (m - a[1][j] >= (n - 1) * 2 && m - a[1][j] <= (n - 1) * 7) {
//记录最优解位置
i = j;
//更改剩余火柴数
m -= a[1][j];
n--;
break;
}
}
//i == -1说明最优解条件不成立
if (i == -1) return "0";
sb.append(a[0][i]);
}
return sb.toString();
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
System.out.println(maxSum(m, n));
}
}
样例
输入：
20
7
输出：
9771111
欢迎提出更多的解法
