51Nod 1499 进制转化问题。

╰半橙微兮° 2022-08-19 15:17 49阅读 0赞

题意：

现在有好多种砝码，他们的重量是 w0,w1,w2,...  每种各一个。问用这些砝码能不能表示一个重量为m的东西。

分析：

题目被分到贪心算法了，可是我没有想到贪心的解法。

这题我是这样想的，如果一个数m只是用w，w^1.....来表示的话，那这个数字m化成w进制其中肯定只有数字0和1，但现在我们要求的数字n是需要两个不同的m相减得到的，并且这两个m的同一位不能同时出现1.现在就是要求给出一个n能不能有两个这样不同的m相减得到。

我们可以利用n的w进制数字来一步一步的判断，利用是否被借位。具体看代码。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        long long w,m;
        int a[100];
        int num,ans,flag;
        while(scanf("%lld%lld",&w,&m)==2)
        {
            memset(a,0,sizeof(a));
            num = 0 ;
            while(m)
            {
                a[num++]=m%w;
                m/=w;
            }
    //        for(int i = num-1 ; i >= 0 ; i--)
    //        {
    //            cout<<a[i]<<" ";
    //        }
    //        cout<<endl;
            //cout<<w<<endl;
            ans = 0 ;
            flag = 0 ;
            for(int i = 0 ; i < num ; i++)
            {
                if(ans==0)   //没有被借位
                {
                    //cout<<a[i]<<endl;
                    if(a[i]==0||a[i]==1)
                    {
                        ans = 0 ;
                    }
                    else if(a[i]==(w-1))
                    {
                        ans = 1 ;
                    }
                    else flag = 1;
    
                }
                else //被借位了
                {
                    if(a[i]==0)
                    {
                        ans = 0 ;
                    }
                    else if(a[i]==w-1||a[i]==w-2)
                    {
                        ans = 1 ;
                    }
                    else flag = 1 ;
                }
                //cout<<ans<<" "<<flag<<endl;
                if(flag==1)break;
            }
            if(flag==0)
            {
                printf("YES\n");
            }
            else printf("NO\n");
        }
        return 0;
    }