本文主要是介绍51nod 1449 砝码称重（经典贪心+进制），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
现在有好多种砝码，他们的重量是 w0,w1,w2,... 每种各一个。问用这些砝码能不能表示一个重量为m的东西。
样例解释：可以将重物和3放到一个托盘中，9和1放到另外一个托盘中。
Input
单组测试数据。 第一行有两个整数w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。
Output
如果能，输出YES，否则输出NO。
Input示例
3 7
Output示例
YES
题解：
贪心
若没有天平，n这个数就是0 1组成的w进制的数
若有天平，n这个数就是 两个 0 1 组成的数之差
即只有下面四种情况：
0-0=0 1-0=1 0-1=w-1（向高位借一后） 1-1=0
分为三大类：
第一大类：相应位数之差为0 1的就很明了
第二大类：相应位数之差为w-1的，借位后的那一位在后面给它加上 1 就好了
第三大类：其余情况就是无解了
#include<stdio.h>int main()
{int n,w;while(scanf("%d%d",&w,&n)!=EOF){int temp,flag=1;while(n){temp=n%w;if(temp==1||temp==0)n/=w;else if(temp==w-1)n=(n+1)/w;else{flag=0;break;}}if(flag) puts("YES");else puts("NO");}return 0;
}
这篇关于51nod 1449 砝码称重（经典贪心+进制）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
