砝码称重问题：1449贪心算法高效解决1秒内完成

1449 砝码称重
1 秒 131,072 KB 40 分 4 级题
现在有好多种砝码&＃xff0c;他们的重量是 w0,w1,w2,... 每种各一个。问用这些砝码能不能表示一个重量为m的东西。

样例解释&＃xff1a;可以将重物和3放到一个托盘中&＃xff0c;9和1放到另外一个托盘中。

思路&＃xff1a;

w进制算法&＃xff0c;
如果没有天平&＃xff0c;只是这些砝码表示m的话&＃xff0c;只需要将m表示成w进制数&＃xff0c;然后要求每一位不是0就是1.(每个质量的砝码只有一个&＃xff0c;要么放&＃xff0c;要么不放)
现在有这个天平&＃xff0c;n这个数就是 两个 0 1 组成的数之差
因为有借位问题&＃xff0c;相差为1是可以的
即只有下面四种情况&＃xff1a;

0-0&＃61;0 1-0&＃61;1 0-1&＃61;w-1&＃xff08;向高位借一后&＃xff09; 1-1&＃61;0

分为三大类&＃xff1a;

第一大类&＃xff1a;相应位数之差为0 1的就很明了

第二大类&＃xff1a;相应位数之差为w-1的&＃xff0c;借位后的那一位在后面给它加上 1 就好了

第三大类&＃xff1a;其余情况就是无解了

代码&＃xff1a;

package _51_node.greedy;import java.util.Scanner;public class ex_1449 {/*** 1449 砝码称重* 1 秒 131,072 KB 40 分 4 级题*

* w进制算法&＃xff0c;* 如果没有天平&＃xff0c;只是这些砝码表示m的话&＃xff0c;只需要将m表示成w进制数&＃xff0c;然后要求每一位不是0就是1.(每个质量的砝码只有一个&＃xff0c;要么放&＃xff0c;要么不放)*

* 现在有这个天平&＃xff0c;n这个数就是 两个 0 1 组成的数之差* 因为有借位问题&＃xff0c;相差为1是可以的* 即只有下面四种情况&＃xff1a;** 0-0&＃61;0 1-0&＃61;1 0-1&＃61;w-1&＃xff08;向高位借一后&＃xff09; 1-1&＃61;0** 分为三大类&＃xff1a;** 第一大类&＃xff1a;相应位数之差为0 1的就很明了** 第二大类&＃xff1a;相应位数之差为w-1的&＃xff0c;借位后的那一位在后面给它加上 1 就好了** 第三大类&＃xff1a;其余情况就是无解了** &＃64;param args*/public static void main(String[] args) {Scanner cin &＃61; new Scanner(System.in);int w &＃61; cin.nextInt();int n &＃61; cin.nextInt();boolean flag &＃61; true;while (n !&＃61; 0) {if (n % w &＃61;&＃61; 0 || n % w &＃61;&＃61; 1) n /&＃61; w;else if ((n &＃43; 1) % w &＃61;&＃61; 0) n &＃61; (n &＃43; 1) / w;else {flag &＃61; false;break;}}if (flag) System.out.println("YES");else System.out.println("NO");}
}