题解 | #人民币转换# 前后缀分治，递归处理

思想

对于给定字符串，按照 亿、万、仟、佰、拾 依次根据字符串长度找到最高级别单位划分前后缀，递归处理。

举例

12031,0200,3002
我们先考虑没有小数的情况（小数很简单最后处理）。
len = 13 ，13 - 1对8整除商大于0，所以最高位是亿。那么答案必然是 xxx亿xxx.（减1是因为我们只判断最高位后面的字符串长度）
此时我们对原字符串划分前后缀，依次递归判断：
prefix = 12031
suffix = 02003002
前后缀最高级别单位是万.

细节处理

1. 零的处理
   当某一段全为零时，如50000，前缀5 + 单位万 + 后缀0000. 后缀全为0，我们直接全部略过。
   当某一段的前半段为零，后半段存在非零的数时，如50050,前缀5 + 单位万 + 后缀0050. 此时从后缀第一个零开始到第一个非零数，只取一个零。
   问题来了，因为我们是递归处理，会将后缀 0050划分成 零千零百五十。所以我们必须在进入后缀递归之前处理这一段零。即：
   前缀5（递归处理） + 单位万 + 零（处理零）+ 后缀50（递归处理）。
2. "壹拾"的处理
   根据题意，需要将所得答案中的所有“壹拾”换成“拾”。
3. 其余部分处理起来很简单，请直接看代码。

my solution

#include <bits/stdc++.h>

using namespace std;

const int N = 10;
string NUMS[N] = {"零", "壹", "贰", "叁", "肆", "伍", "陆", "柒", "捌", "玖"};
string res;


inline bool contains_only_zero(string &s)
{
    bool res = true;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != '0') {
            res = false;
            break;
        }
    }
    return res;
}

inline void handle_suffix_zero(string &suf)
{
    if (res.size() > 1 && suf[0] == '0' && !contains_only_zero(suf)) res += "零";
    int i = 0;
    for (; i < suf.size() && suf[i] == '0'; i++);
    suf = suf.substr(i, suf.size() - i);
}

void dfs(string &zz)
{
    if (contains_only_zero(zz) || !zz.size()) {    // if zz only 0
        return;
    }
    int l = zz.size() - 1;
    if (!l) {
        //cout << NUMS[zz[0] - '0'];
        res += NUMS[zz[0] - '0'];
        return;
    }

    int y = (int) l / 8;
    if (y > 0) {
        string pre = zz.substr(0, zz.size() - 8);
        dfs(pre);
        //cout << "亿";
        res += "亿";
        string suf = zz.substr(pre.size(), 8);
        handle_suffix_zero(suf);
        //cout << suf << endl;
        dfs(suf);
        return;
    } 
    int w = (int) l / 4;
    if (w > 0) {
        string pre = zz.substr(0, zz.size() - 4);
        dfs(pre);
        //cout << "万";
        res += "万";
        string suf = zz.substr(pre.size(), 4);
        handle_suffix_zero(suf);
        //cout << suf << endl;
        dfs(suf);
        return;
    }
    int q = (int) l / 3;
    if (q > 0) {
        string pre = zz.substr(0, zz.size() - 3);
        dfs(pre);
        //cout << "仟";
        res += "仟";
        string suf = zz.substr(pre.size(), 3);
        handle_suffix_zero(suf);
        //cout << suf << endl;
        dfs(suf);
        return;
    }
    int b = (int) l / 2;
    if (b > 0) {
        string pre = zz.substr(0, zz.size() - 2);
        dfs(pre);
        //cout << "佰";
        res += "佰";
        string suf = zz.substr(pre.size(), 2);
        handle_suffix_zero(suf);
        //cout << suf << endl;
        dfs(suf);
        return;
    }
    int s = (int) l / 1;
    if (s > 0) {
        string pre = zz.substr(0, zz.size() - 1);
        dfs(pre);
        //cout << "拾";
        res += "拾";
        string suf = zz.substr(pre.size(), 1);
        handle_suffix_zero(suf);
        //cout << suf << endl;
        dfs(suf);
        return;
    }
}


inline void helper(string &zz, string &xx)
{
    // 处理“壹拾“问题。当它出现在首部或者前面跟0时，仅用“拾”，其他情况用“壹拾”
    for (size_t a = res.find("壹拾"); a != res.npos; a = res.find("壹拾"))
        res.replace(res.find("壹拾"), strlen("壹拾"), "拾");

    res = "人民币" + res;

    if (res != "人民币")
        res += "元";

    if (xx == "" || contains_only_zero(xx)) {
        res += "整";
    }
    else {    // 处理小数部分
        for (int i = 0; i < xx.size(); i++) {
            if (xx[i] == '0') continue;
            res += NUMS[xx[i] - '0'];
            if (!i) res += "角";
            else res += "分";
        }
    }
}

void solve(string s) 
{
    string zz = "", xx = "";
    bool is_x = false;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '.') {
            is_x = true;
            continue;
        }
        if (is_x) xx += s[i];
        else zz += s[i];
    }
    dfs(zz);
    helper(zz, xx);
    cout << res << endl;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    string s;
    for (; cin >> s; res = "")
        solve(s);
    return 0;
}