题意：

输入一个数字金额，输出其中文表示法。

解法（高精度版本）

本题解中我们实现一个支持任意大小数字的转换程序

我们举个例子，比如数字： $898944323$

该数字的中文表示法为： $捌亿玖仟捌佰玖拾肆万肆仟叁佰贰拾叁$

首先，我们将该数字从右到左四个四个分块，不足的部分单独一块

可得到： $8,9894,4323$

对应的，我们再将中文表示法按照对应数字进行分块： $捌亿,玖仟捌佰玖拾肆万,肆仟叁佰贰拾叁$

我们可以发现，我们从右到左从第二块开始，分别给每一块加一个『单位』（万、亿、万亿、亿亿、万亿亿、亿亿亿、万亿亿亿......）后，再在『单位』前加上当前块的数字的中文表示法，就是答案。

所以，我们只需要求出最多四位数字对应的中文表示法然后再加上对应块的『单位』，即可求解本题。

接下来，我们考虑如何求解最多四位数字的中文表示法：

显然，只需要在从右到左第二位开始，分别加上对应单位（拾、佰、仟）即可，注意：如果第二位数值是1，要特殊判断，本题中不能输出『壹拾』，而是直接输出『拾』

接下来我们考虑有数字0的情况：

我们对数字串从右到左扫描

1. 首先我们考虑数字串结尾有很多0的情况，比如： $8900000000000000000000$ 这样的

那么，我们可以首先从右到左进行扫描，找到第一个不是整块都是数字0的块，然后从当前块开始求解。

2. 接下来我们对块内考虑：

（1）如果结尾数字是0，我们同样是按照上面的策略，在块内从右到左进行扫描，找到第一个非0数，然后从当前数字开始求解。

（2）其他情况，我们只需要在块内从右到左扫描的过程中将连续的0作为一整段，在当前答案前追加一个『零』即可。

3. 接下来我们对块与块之间进行考虑：

我们可以参照上述策略，如果当前块从左到右第1位是数字0，则表示对于当前块来说，答案前面要加一个『零』，同样的，如果当前块前面一块整块都是数字0，则可以直接跳过。

代码：

#include<bits/stdc++.h>
using namespace std;
string lft,rgt,d;
inline void init(){
    //处理输入的数据，将输入的浮点数分为整数部分lft和小数部分rgt
    int idx=0;
    while(idx<d.size()&&d[idx]!='.'){
        lft.push_back(d[idx]);//整数部分
        idx++;
    }
    idx++;
    while(idx<d.size()){
        rgt.push_back(d[idx]);//小数部分
        idx++;
    }
}
string txt[]={"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"};//对应数位所对应的中文
string a[]={"拾","佰","仟"};//块内的『单位』
vector<string> f;//f[i]表示：若第i位刚好是块尾，则表示对应的『单位』，否则作占位使用
inline bool check_all_zero(const string& s){
    //判断数字串s是否全部是0
    for(int i=0;i<s.size();i++){
        if(s[i]!='0')return false;
    }
    return true;
}
inline string clear_front_zero(string& s){
    //对于数字串s，范围清除其前导0后的数字串
    string res;
    int idx=0;
    while(idx<s.size()&&s[idx]=='0')idx++;
    while(idx<s.size())res.push_back(s[idx++]);
    return res;
}
inline vector<string> sub_to_ans(string s){
    //返回最多四位的数字串对应的中文串
    vector<string> res;
    if(check_all_zero(s))return res;
    s=clear_front_zero(s);//首先清除前导0
    reverse(s.begin(),s.end());//翻转，将从右到左枚举转换为从左到右枚举
    int idx=0;
    if(s[idx]=='0'){
        //如果数字串最后一段是0，则先特殊处理
        while(idx<s.size()&&s[idx]=='0')idx++;
        res.push_back(a[idx-1]);
        if(idx!=1||s[idx]!='1'){
            res.push_back(txt[s[idx]-'0']);
        }
        idx++;
    }else{
        //由于数字串最后一位没有『单位』，先处理最后一位
        res.push_back(txt[s[idx]-'0']);
        idx++;
    }
    while(idx<s.size()){
        if(s[idx]=='0'){
            //连续的0统一处理
            while(idx<s.size()&&s[idx]=='0')idx++;
            res.push_back(txt[0]);//追加中文『零』
            res.push_back(a[idx-1]);//追加对应单位
            if(idx!=1||s[idx]!='1'){//如果不是 拾
                res.push_back(txt[s[idx]-'0']);//追加对应数字中文表示法
            }
            idx++;
        }else{
            res.push_back(a[idx-1]);//追加对应单位
            if(idx!=1||s[idx]!='1'){
                res.push_back(txt[s[idx]-'0']);//追加对应数字中文表示法
            }
            idx++;
        }
    }
    return res;
}
inline void add_vector(vector<string>& x,vector<string>& y){
    //将x数组后面追加y数组
    for(int i=0;i<y.size();i++){
        x.push_back(y[i]);
    }
}
inline void out_rgt(){
    //处理小数部分
    if(check_all_zero(rgt)){
        cout<<"整";
        //如果小数部分全部是0
    }else{
        if(rgt[0]!='0'){
            cout<<txt[rgt[0]-'0']<<"角";
        }
        if(rgt.size()>1&&rgt[1]!='0'){
            cout<<txt[rgt[1]-'0']<<"分";
        }
    }
}
inline void work(){
    if(check_all_zero(lft)&&check_all_zero(rgt)){
        cout<<"人民币零元"<<endl;
        //特判
        return;
    }else if(check_all_zero(lft)){
        //如果整数部分是0
        cout<<"人民币";
        out_rgt();
        cout<<endl;
        return;
    }
    reverse(lft.begin(),lft.end());//翻转整数部分，将从右到左枚举转换为从左到右枚举
    f.push_back("");//占位
    for(int i=1;i<lft.size();i++){
        if(i%4==0){
            //添加『单位』
            if(i==4){
                f.push_back("万");
            }else if(i==8){
                f.push_back("亿");
            }else{
                if(i%8==0){
                    f.push_back("亿"+f[i-8]);
                }else{
                    f.push_back("万"+f[i-4]);
                }
            }
        }else{
            f.push_back("");//占位
        }
    }
    vector<string> ans;//答案数组
    bool las_zero=false;//之前是否追加了『零』
    for(int i=0;i<lft.size();i+=4){
        string tmp=lft.substr(i,min(4,(int)lft.size()-i));//取当前块的最多4个数位
        reverse(tmp.begin(),tmp.end());//由于前面已经将整个整数翻转了，所以这边要将子串翻转回来
        if(check_all_zero(tmp)){
            //如果当前块的数字全部是0
            if(!las_zero){
                las_zero=true;
                ans.push_back(txt[0]);
            }
        }else{
            if(i>0)ans.push_back(f[i]);//追加单位，第一块没有单位
            vector<string> t=sub_to_ans(tmp);//当前块对应的数字中文表示法
            add_vector(ans,t);//追加到答案数组中
            if(tmp[0]=='0'){//如果当前块从左到右第1位是0
                if(!las_zero){
                    las_zero=true;
                    ans.push_back(txt[0]);
                }
            }else{
                las_zero=false;
            }
        }
    }
    reverse(ans.begin(),ans.end());//由于答案是每次向后追加的，对应实际是在最前端插入，所以最后要将答案翻转
    cout<<"人民币";
    for(int i=0;i<ans.size();i++){
        cout<<ans[i];
    }
    cout<<"元";
    out_rgt();
    cout<<endl;
}
inline void clear_all(){
    //多测清空
    lft.clear();
    rgt.clear();
    f.clear();
    d.clear();
    lft.shrink_to_fit();
    rgt.shrink_to_fit();
    f.shrink_to_fit();
    d.shrink_to_fit();
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>d){
        init();
        work();
        clear_all();
    }
    return 0;
}

时间复杂度： $O(n)$ ，其中 $n$ 代表数位长度。显然我们只需要扫描一遍数字串即可，对于数字串的每一位，我们只需要 $O(1)$ 的时间复杂度来处理，故总的时间复杂度为 $O(n)$

空间复杂度： $O(1)$ ，我们需要 $O(1)$ 的空间存储答案数组，单位数组，辅助字符串，空间复杂度为 $O(1)$ 。

题解 | #人民币转换#

题意：

解法（高精度版本）