题解：P6547 [COCI2010-2011#2] NAPOR
刚开始做这道题，最先想到的便是字符串与 int 之间的转换。
对于第 $n_i$ 行整行输入，若输入数字，则需要在下一个不是数字的位置的地方记录，然后把所得数字加入答案中。当然，答案为 ans = ans * 10 + str[i] - '0'。同时，题目中的 他还必须省略文本中数字可能包含的任何前导零 这句话十分关键，因此数字 $0$ 需要特判。最后，因为 在文本中找到所有数字，并以不降序的顺序输出，所以需要进行一次排序。
于是我们就得到了以下这个代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 550;
int a[MAX];
int main()
{
int n,k = 0,tmp;
string str;
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>str;tmp = 0;
bool ok = 0;
for(int j = 0;j < str.size();j++)
{
if('0' <= str[j] && str[j] <= '9') tmp = tmp * 10 + str[j] - '0',ok = 1;
else
{
if(ok) a[++k] = tmp;
tmp = 0,ok = 0;
}
}
if(ok) a[++k] = tmp;
}
sort(a + 1,a + k + 1);
for(int i = 1;i <= k;i++) cout<<a[i]<<endl;
return 0;
}
|
当然，这个思路也许只能过 $1-2$ 个测试点，原因很简单 每个字符串长度不超过 100，因此当该字符串全部为数字时，肯定会爆 long long。那么如何解决呢？
全部都使用字符串来记录数字！ 把所得的数字加入答案中，这次的加法与上面不一样，因为都是字符串，所以我们只要 ans += str[i]。
同时，前导 $0$ 的出现同样是关键，我们以题目中的样例 $3$ 为例，我们在这 $n$ 行全部输入完毕后，会依次得到这几个数字：
01 02 007 03 04 000。所以我们在排序之前需要删除前导 $0$，当然，答案为 $0$ 的情况我们依然要注意，核心代码(有注释)：
1
2
3
4
5
6
7
8
9
10
11
| for(int i = 1;i <= k;i++)
{
tmp = "";bool ok = 0;
for(int j = 0;j < a[i].size();j++)
{
if(a[i][j] != '0') ok = 1;
if(ok) tmp += a[i][j];
}
if(ok) a[i] = tmp;
else a[i] = '0';
}
|
经过处理，这几个数字就变成了：1 2 7 3 4 0。于是乎，接下去就是排序了。排序时是将两个字符串进行比较，所以需要一个 bool cmp(string x,string y) 函数。这两个字符串所组成的数有两种情况(为表示方便，以下 string x 的长度为 $sx$，string y的长度为 $sy$)：
① $sx = sy$ 数位相同，我们需要逐一进行比较，即 return x < y;
② $sx \neq sy$ 数位不同，更加方便，直接比较数位大小，即 return sx < sy;
经过这样的分析，最后我们排序后只需要逐一输出即可，一行一个。最后是 AC 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 550;
string a[MAX];
bool cmp(string x,string y)
{
if(x.size() != y.size()) return x.size() < y.size();
else return x < y;
}
int main()
{
int n,k = 0;
string str,tmp;
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>str;tmp = "";
bool ok = 0;
for(int j = 0;j < str.size();j++)
{
if('0' <= str[j] && str[j] <= '9') tmp += str[j],ok = 1;
else
{
if(ok) a[++k] = tmp;
tmp = "",ok = 0;
}
}
if(ok) a[++k] = tmp;
}
for(int i = 1;i <= k;i++)
{
tmp = "";bool ok = 0;
for(int j = 0;j < a[i].size();j++)
{
if(a[i][j] != '0') ok = 1;
if(ok) tmp += a[i][j];
}
if(ok) a[i] = tmp;
else a[i] = '0';
}
sort(a + 1,a + k + 1,cmp);
for(int i = 1;i <= k;i++) cout<<a[i]<<endl;
return 0;
}
|
