题目大意:给出一个不超过20位的整数,判断它的两倍的结果是否是原有的数字的一个排列。
unsigned long long 最多表示到 2^64 - 1,小于 10^20,所以要用大数加法的方式去得到两倍的结果,存储在vector<int>中,然后将原数和两倍分别排序,比较排序后的两个vector是否相同即可。
AC代码如下:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
bool isPermuation(vector<int> &v, vector<int> &ans)
{
int carry = 0;
for (int i = v.size() - 1; i >= 0; --i)
{
int tmp = v[i] * 2 + carry;
if(tmp >= 10)
{
ans.push_back(tmp - 10);
carry = 1;
}
else
{
ans.push_back(tmp);
carry = 0;
}
}
if(carry == 1)
{
ans.push_back(1);
return false;
}
vector<int> ansCopy = ans;
sort(ansCopy.begin(), ansCopy.end());
sort(v.begin(), v.end());
if(v != ansCopy) return false;
return true;
}
int main()
{
string str;
cin >> str;
vector<int> v, ans;
for (int i = 0; i < str.size(); ++i)
{
v.push_back(str[i] - '0');
}
bool flag = isPermuation(v, ans);
if(flag) printf("Yes\n");
else printf("No\n");
for (int i = ans.size() - 1; i >= 0; --i)
{
printf("%d", ans[i]);
}
return 0;
}