import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int a = in.nextInt(); System.out.println(calc(a)); } } /** * 这个题目写了其他的解法,但是经过思考后觉得题目中的3种货物的重量如果发生变化后,在一些特殊组合的时候 * 之前的方法就会有漏洞,觉得下面的解题思路才能覆盖货物变化后的结果 * case1:当货物的重量分别为:8 6 2的时候,x总重量为20,之前的解题思路(calcOld方法), * 可能结果为:8,8,2,2;实际结果为:8,6,6 * case2:当货物的重量分别为:9 4 3的时候,x总重量为12,如果按照先从重的货物组合的话, * 可能会得到结果为:4,4,4;实际结果为:9,3 * 所以为了覆盖所有可能,需要将所有组合计算出来,最后取出最少的一组,第一种组合,最重的一种;第二种组 * 合为最终的两种货物;第三种组合为从重到轻依次递减组合,也就是最早的解题思路(calcOld方法) * 最终的算法算是对题目的升级版,也就是说货物重量和箱子的载重都可变 */ private static int calcOld(int a) { int h1 = 3; int h2 = 5; int h3 = 7; int max7 = a / h3; int max5 = 0; int max3 = 0; int i7 = max7; int i5 = 0; int i3 = 0; for (; i7 >= 0; i7--) { max5 = (a - i7 * h3) / h2; int a2 = (a - i7 * h3); i5 = max5; for (; i5 >= 0; i5--) { if ((a2 - i5 * h2) % h1 == 0) { max3 = (a2 - i5 * h2) / h1; return (i7 + i5 + max3); } } } return -1; } private static int calc(int a) { int h1 = 3; int h2 = 5; int h3 = 7; // 最重的货物直接装满 if(a % h3 == 0){ return a / h3; } // 尝试用最重的两种货物装满 int result1 = -1; int n1 = a / h3; while(n1 >= 0){ int unUse1 = a - n1 * h3; if(unUse1 % h2 == 0){ // 满足条件,退出循环 result1 = n1 + unUse1 / h2; break; } // 去掉一个最重的货物再尝试 n1--; } // 最后尝试三种货物组合 int result2 = -1; n1 = a / h3; // 是否结束循环 boolean flag = false; while(n1 >= 0){ int unUse1 = a - n1 * h3; int n2 = unUse1 / h2; while(n2 >= 0){ int unUse2 = unUse1 - n2 * h2; if(unUse2 % h1 == 0){ result2 = n1 + n2 + unUse2 / h1; flag = true; break; } n2--; } if(flag){ break; } // 去掉一个最重的货物再尝试 n1--; } if(result1 == -1){ // 当最重的两种货物组合无法装满时,返回三种货物组合结果 return result2; } if(result2 == -1){ // 当三种货物组合无法装满时,返回最重的两种货物组合结果 return result1; } if(result1 == -1 && result2 == -1){ // 所有组合都无法装满 return -1; } // 当最终的两种货物组合和三种货物组合都能装满时,返回数量最少的那个组合结果 return result1 > result2 ? result2 : result1; } }