题解 | #扭蛋机# 贪心策略
扭蛋机
https://www.nowcoder.com/practice/9d26441a396242a9a0f7d2106fc130c7
要想达到用的最少次数，最终的情况肯定是将手里的球全部塞进扭蛋机然后得到最终的答案。因为这样每次得到的球更多，因此可以减小次数。
2号扭蛋机可以得到奇数个扭蛋，3号可以得到偶数个扭蛋。因此对于给定的个数N，始终可以通过其中一个扭蛋机得到。因此我们可以反推，比如当N = 10 时。可以从3号扭机蛋塞4个球得到。这4个球可以通过3号扭蛋机塞1个球得到。这1个球可以通过2号扭蛋机塞0个球得到。
这样下来每次扭蛋都把手里的球用完，都能得到最多的球，因此这个策略是最优的，所以答案就是"233"。迭代求解即可。
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt();
long num = (long)n;
StringBuilder sb = new StringBuilder();
while(num != 0){
if(num % 2 == 0){
sb.append(("3"));
num = (num - 2) / 2;
}else{
sb.append("2");
num = (num - 1) / 2;
}
}
System.out.print(sb.reverse().toString());
}
}
查看30道真题和解析