题解 P8243 [COCI2013-2014#3] REČENICE

tracyyi · 2022-03-28 00:14:03 · 题解

题意简述

• 输入整数 n 个字符串，代表 n 个单词。

• 替换英文数字，数字表示所有单词的总长度，包括替换后的英文数字。

• 把所有单词依次输出。

题目分析

需要解决下边两个问题：

1. 把整数用英文表示出来

先看数据范围，数字不超过 1000 ，所以只考虑 3 位数的情况（我没考虑刚好 1000 ）的情况，应该不太容易编出这样的测试点，赌一把啰，不过加上也不难。

分析一下英文数字的组成：

• 如果是三位数，百位再加上 "hundred".

• 对于低两位，如果大于等于 20 的，十位数需要单独表示，事先写入一个字符串数组 shi[10] .

• 如果低两位小于 20 ，即从 1 到 19 ，各有一个单词，放在字符串数组 ge[20] 中。

2. 凑字数

即把英文数字刚好表示总长度。这里我用暴力枚举，首先算出其余单词的字符数，然后往上加。因为没有哪个数字小于 3 个字符，所以直接从 3 开始往上加，每加一个算一下总长度，如果发现符合，就结束，最后输出结果。数字的总长度不会超过 100 ，所以枚举 3 到 100 就好。

下边是源代码。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string s[22], numstr;
stack <int>sk;
string ge[]={"","one","two","three","four","five",
            "six","seven","eight","nine","ten","eleven",
            "twelve","thirteen","fourteen","fifteen",
            "sixteen", "seventeen", "eighteen", "nineteen"};
string shi[]={"","","twenty","thirty", "forty", "fifty",
                    "sixty","seventy","eighty","ninety"};

//把整数转换成英文
string convert(int n){
    int t=n;
    string ans="";
//先清空栈
    while(!sk.empty()){
        sk.pop();
    }   

//用栈来保存每一位，本来三位数不用这么麻烦，
//但为了以后扩展成更多位数，常规来写。
    while(t>0){
        sk.push(t%10);
        t=t/10;
    }

 //先处理百位
    if(sk.size()==3){
        ans=ans+ge[sk.top()]+"hundred";
        sk.pop();
    }
 //处理低两位
    if(sk.size()==2){
        if(sk.top()>1){
            ans=ans+shi[sk.top()];
            sk.pop();
        }else{
            n=n%100;//低两位是0~19 
            ans=ans+ge[n];
            return ans;
        }
    }
//处理个位
    if(sk.size()==1){
        ans=ans+ge[sk.top()]; 
    }
    return ans;
}

int main(){
    int n, sm=0, id=0;
    cin>>n;
    cin.ignore();
    for(int i=1; i<=n; i++){
        cin>>s[i];
        if(s[i]!="$"){
            sm=sm+s[i].size();
        }else{
            id=i;//记录数字所在的位置 
        }
    }

    // 验证一下转换函数，OK了再往下写
    //  numstr=convert(sm);
    //  cout<<sm<<endl;
    //  for(int i=1; i<=999; i++){
    //      cout<<convert(i)<<endl;
    //  }

    //开始凑字数，在原长度基础上加i，再算算增加了几个字符
        for(int i=3; i<=100; i++){
            numstr=convert(sm+i);
            if(numstr.size() == i){
                s[id]=numstr;
                //cout<<i<<" "<<numstr<<endl;
                break;
            }
        }

    //大功告成，一起输出！
        for(int i=1; i<=n; i++){
            cout<<s[i]<<" ";
        }

        return 0;
    }