题解 P6547 【[COCI2010-2011#2] NAPOR】

· · 题解

P6547 题解

题目的意思很简单，给出一堆字符，让你在这堆字符中找出数字，并将它们从大到小输出。

由于题中给出了 n 个字符串，所以我们大可对于每一行分别操作。

我们令这一行的字符串为 s ， l 为当前行字符的长度， i 为当前指向的字符，容易得到这三个while循环（传统艺能）：

while(i<l)  //大边界，便于在扫完整个字串后退出循环
{
    while(s[i]>='0'&&s[i]<='9')  //当前字符是数字时
    //...
    while(s[i]>='a'&&s[i]<='z')  //当前字符是小写字母时
    //...
}

看看注解就好，应该不需要多做什么解释。

题中的要求是找出数字，所以在“数字”的while循环里，我们可用以下的代码

sum=sum*10+s[i]-48;  //将字符转换成数字，再累积到计数器中

满足这个要求。

在退出循环后，我们开一个栈把数字存进去，最后按要求排序即可。

for(re x=1;x<=n;x++)
{
    std::cin>>s;
    l=s.length();  //输入&计算长度 

    re i=0;
    while(i<l)
    {
        re sum=0,p=0;  //定义局部变量 
        while(s[i]>='0'&&s[i]<='9')
        {
            p=1;  //判断这一次是否进行了“数字累加”这一过程 
                        sum=sum*10+s[i]-48;
            i++;  //扫描下一个字符 
        }
        if(p==1)
            a[++t]=sum;  //存入栈中 
        while(s[i]>='a'&&s[i]<='z')
            i++;  //扫描下一个字符 
    }
}

但是！！！

这样写乍一看是正确的，样例也过了，交上去评测却只有 12 分。

我们仔细看看数据范围：

“每个字符串长度不超过 100 ”

那万一这一行字符全是数字呢？这样一来，不但是 int，就算是 unsigned\ long\ long 也是存不下的。

那我们就得改变思路了，不用数组，而是用 string 类型的数组来存。（至于为什么不用 char ，原因是 char 不论是在累加方面还是排序方面，都没有 string 方便（C++万岁））

我们定义一个 string 数组 ans_i ，表示答案。对于每一行字符，再定义一个 string 型 tmp ，表示当前存储的这个“数字”。需要注意的是，我们应该将 tmp 的初值赋为""，这是空串。

我们可以用语句：

tmp+=s[i];

将字符 s_i 接在这个字符串的后面，起到与上面说的 sum 语句起到同样的效果。但这样的做法无法去除前导零，因此，我们需要在退出循环后，手动为其去除前导零。代码如下：

t++;
re j=0,k=tmp.length();  //计算这个“数字”的长度 ，从第一个字符开始扫描 
while(tmp[j]=='0'&&j<k-1)  //当当前字符为‘0’并且不是最后一个字符时（答案存在0） 
    j++;  //删去 
for(re y=j;y<=k;y++)
    ans[t]+=tmp[y];  //将未删去的字符接在ans后

然后排序输出即可：

std::sort(ans+1,ans+t+1);

for(re i=1;i<=t;i++)
    std::cout<<ans[i]<<endl;

但是#2！！！

这样的排序其实是有问题的。简单地说说 algorithm 库中对 string 型的排序方法：首位越大的排越前面。

就拿本题的样例二说吧，正确的 sorting 应该是：

0,2,2,43,231233

但上述写法的输出则是：

0,2,2,231233,43

懂我意思了吧？

所以最后摆在我们面前的问题只有一个：手写 cmp 函数。

首先把 ans_i 数组改为结构体（方便以长度为关键字比较）：

struct Ans
{
    int len;  //存长度
    string a;  //存“数字”本身
}ans[501];

接着写 cmp 函数（详见注释）：

inline bool cmp(Ans x,Ans y)
{
    if(x.len==y.len)  //若长度相等 
        return x.a<y.a;  //则按string型的默认排序方式排序 
    return x.len<y.len;  //位数多的肯定比位数少的大 
}

最后一个一个把主函数里的 ans_i 改成 ans_i.a 就可以了。

完整代码如下：

#include <bits/stdc++.h>
#define re register int
using namespace std;

int n,l,t;
string s;
struct Ans
{
    int len;
    string a;
}ans[501];

inline bool cmp(Ans x,Ans y)
{
    if(x.len==y.len)
        return x.a<y.a;
    return x.len<y.len;
}

int main()
{
    std::cin>>n;

    for(re x=1;x<=n;x++)
    {
        std::cin>>s;
        l=s.length();

        re i=0;
        while(i<l)
        {
            re p=0;
            string tmp="";
            while(s[i]>='0'&&s[i]<='9')
            {
                p=1;
                tmp+=s[i];
                i++;
            }
            if(p==1)
            {
                t++;
                re j=0,k=tmp.length();
                while(tmp[j]=='0'&&j<k-1)
                    j++;
                for(re y=j;y<=k;y++)
                    ans[t].a+=tmp[y];
                ans[t].len=ans[t].a.length();
            }
            while(s[i]>='a'&&s[i]<='z')
                i++;
        }
    }

    std::sort(ans+1,ans+t+1,cmp);

    for(re i=1;i<=t;i++)
        std::cout<<ans[i].a<<endl;

    return 0;
}

码字不易，还请看官点赞！