题134.pat甲级练习-1023 Have Fun with Numbers (20 分)

一、题目

在这里插入图片描述

二、题解

看到题目说输入的数位数最多为20你就可以断定用普通的乘2得到结果进行比对肯定不行，因为数太大了，这时候我们自然就会想到用模拟竖式乘法来处理它。

#include <bits/stdc++.h>

using namespace std;

map<int,int> m;

int main()
{
   string num;
   cin>>num;
   for(int i=0;i<num.length();i++)
   {
       m[num[i]-'0']++;
   }
   vector<int> temp(num.length()+1);//存进位的数组
   stack<int> res;
   int flag=1;
   temp[temp.size()-1]=0;//数字的最低位的进位先初始为0
   int i;
   for(i=num.length()-1;i>=0;i--)
   {
       int res0=(num[i]-'0')*2;
       res.push(res0%10+temp[i+1]);//每次的结果应为积的个位数加上上轮进位数
       if(m.find(res.top())==m.end()||m[res.top()]==0)//若在输入的数中没有找到该数字或者该数字的数目已经超限了则为No
       {
           flag=0;
       }
       else
       {
           m[res.top()]--;//匹配一个就把对应数字数目减1
       }
       temp[i]=res0/10;//进位数为积的十位上的数
   }
   if(temp[i+1])//最高位之前如果还有进位则当作结果的更高位结果放入栈中
   {
       res.push(temp[i+1]);
   }
   if(!flag||res.size()!=num.length())//注意得到的结果长度和之前不相同自然也是No
   {
       cout<<"No"<<endl;
   }
   else
   {
       cout<<"Yes"<<endl;
   }
   while(!res.empty())
   {
       cout<<res.top();
       res.pop();
   }
}