星空's Blog
星空's Blog
PAT-A1023 Have Fun with Numbers

原题

Have Fun with Numbers (20 分)

题解

输入数据超出了基本数据类型的范围,需要使用string存储
对原序列进行翻倍操作,要注意进位的处理
题目要求检测翻倍前后数字是否还是原来的数字(只是顺序不同)
这里不要求顺序相同,只要求数字出现次数一致

可以用一个大小为10的数组标记"偏移量"
遍历原序列,出现0~9的数字就++,使其"上浮"
遍历输出序列,出现一次就–,使其"下沉"
最后看一下标记数组是否"水平"就可以

对第一个数字>4的输入序列,可以直接认为是No,因为肯定会导致结果多出一个数字,但是题目还要输出它的结果序列,所以还是得进行翻倍操作,最后检测一下进位标识,不要忘了对最后一次进位的处理

对了,string拼接要注意顺序,因为进位是从后往前运算,所以
r = r + "0" — r0
r = "0" + r — 0r

代码

#include <iostream>
#include <string>
using namespace std;

int main(void) { 
    string n = ""; //输入序列 
    string r = ""; //输出序列 
    int log[10] = {0}; 
    bool carry = false; //进位标识 
    int t = 0;
    cin >> n;
    for (int i = n.length() - 1;i >= 0;i--) {
        t = n[i] - '0';
        log[t]++;
        t = t << 1;
        if (carry) {
            if (t > 9) {
                t = t % 10 + 1;
            } else {
                t = t + 1;
                carry = false;
            }
        } else {
            if (t > 9) {
                t = t % 10;
                carry = true;
            }
        }
        log[t]--;
        r = to_string(t) + r;
    }
    if (carry) {
        r = to_string(1) + r;
        cout << "No" << endl;
        cout << r;
        return 0;
    }
    int i = 0;
    for (;i < 10;i++) {
        if (log[i]) {
            cout << "No" << endl;
            break;
        }
    }
    if (i == 10) {
        cout << "Yes" << endl;
    }
    cout << r;
    return 0;
}
所有文章禁止转载。
代码仅供参考
为了对抗广告机器人,首次留言将会被审核
首页      算法学习      PAT-A      PAT-A1023 Have Fun with Numbers

星空

文章作者

发表评论

textsms
account_circle
email

星空's Blog

PAT-A1023 Have Fun with Numbers
原题 Have Fun with Numbers (20 分) 题解 输入数据超出了基本数据类型的范围,需要使用string存储 对原序列进行翻倍操作,要注意进位的处理 题目要求检测翻倍前后数字是否还是原来的数字…
扫描二维码继续阅读
2019-08-15