曾彪彪的个人博客 -- 拼数算法优化

# P1012 [NOIP 1998 提高组] 拼数

## 题目描述

设有 $n$ 个正整数 $a_1 \dots a_n$，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

## 输入格式

第一行有一个整数，表示数字个数 $n$。

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$。

## 输出格式

一个正整数，表示最大的整数

## 输入输出样例 #1

### 输入 #1

```
3
13 312 343
```

### 输出 #1

```
34331213
```

## 输入输出样例 #2

### 输入 #2

```
4
7 13 4 246
```

### 输出 #2

```
7424613
```

## 说明/提示

对于全部的测试点，保证 $1 \leq n \leq 20$，$1 \leq a_i \leq 10^9$。

NOIP1998 提高组 第二题

这题我废了老鼻子劲做出来，代码如下：

```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
-
-
-
test case:
-
3
13 312 343

-
4
7 13 4 246
-
5
5
54
543
5432
54321
-
6
321 32 407 135 13 217
-
5
5
54
543
54399
5439
-
first submit score: 100
cause:

**/

#include <bits/stdc++.h>
using namespace std;

bool compare(string s1, string s2)
{
    int minLen = min(s1.size(), s2.size());
    int start = 0;
    while (start < minLen && s1[start] == s2[start])
    {
        start++;
    }
    if (start >= minLen)
    {
        if (s1.size() < s2.size())
        {
            return s1.back() > s2[start];
        }
        else
        {
            return s1[start] > s2.back();
        }
    }
    return s1[start] > s2[start];
}

int main()
{

int n;
    cin >> n;
    vector<string> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

sort(nums.begin(), nums.end(), compare);

for (auto s : nums)
    {
        cout << s;
    }

// freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    return 0;
}

```

提交了几次才AC，之前错误的地方在于

6
321 32 407 135 13 217
-
5
5
54
543
54399
5439

这两个测试用例过不了，后来调整compare方法才AC。

网上看别人的写法，把compare方法改成如下：
```c++

bool compare(string s1, string s2)
{
    return s1 + s2 > s2 + s1;
}
```

利用等长string进行比较，能想到这样思路的人，是高手，拜服！

拼数算法优化

评论(0)