自动搬运

查看原文

来自洛谷，原作者为

	ZolaWatle За тебя, Родина-матъ.

搬运于2025-08-24 22:21:48，当前版本为作者最后更新于2020-05-12 19:05:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}

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