1038 Recover the Smallest Number（贪心，排序）

柔情只为你懂 2024-04-08 12:57 68阅读 0赞

## 1038 Recover the Smallest Number（贪心） ##

### 0、题目 ###

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given \{ 32, 321, 3214, 0229, 87 \}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

#### Input Specification: ####

Each input file contains one test case. Each case gives a positive integer *N* (≤104) followed by *N* number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

#### Output Specification: ####

For each test case, print the smallest number in one line. Notice that the first digit must not be zero.

#### Sample Input: ####

5 32 321 3214 0229 87

#### Sample Output: ####

22932132143287

### 1、大致题意 ###

给一些字符串，求它们拼接起来构成最小数字的方式

### 2、基本思路 ###

让我们一起来见证 `cmp` 函数的强大之处！！~不是按照字典序排列就可以的，必须保证两个字符串构成的数字是最小的才行，所以 `cmp`函数写成 `return a + b < b + a;` 的形式，保证它排列按照能够组成的最小数字的形式排列。

因为字符串可能前面有`0`，这些要移除掉（用`s.erase(s.begin())`就可以了嗯 `string`如此神奇）。输出拼接后的字符串即可。

**注意：如果移出了0之后发现 `s.length() == 0`了，说明这个数是0，那么要特别地输出这个0，否则会什么都不输出**

### 3、解题思路 ###

#### 3.1 `string` 知识点 ####

我在解题前，复习了[ `string` 库的相关知识点][_string_]，此题主要是 `string` 的 `erase()` 函数，这个函数有2种用法：

*  删除单个元素
 *  删除一个区间内的所有元素
 *  时间复杂度均为O(N)

#include<string>
    #include<iostream>
    using namespace std;
    int main()
    {
        
    	// 删除单个元素
        string ss = "12345";
        cout << "ss: " << ss << " " << endl;
        ss.erase(ss.begin()+4);
        cout << "ss.erase(ss.begin()+24: " << ss << endl;
    	
    	// 删除1个区间内所有元素
        cout << endl;
        ss = "678910";
        cout << "ss: " << ss << " " << endl;
        ss.erase(ss.begin()+2, ss.end()-1);
        cout << "ss.erase(ss.begin()+2, ss.end()-1): " << ss << endl;
    	
    	// 从起始位置，删除x个字符
        cout << endl;
        ss = "678910";
        cout << "ss: " << ss << " " << endl;
        ss.erase(3,3);
        cout << "ss.erase(3,3): " << ss;
    
        return 0;
    }

输出：

ss: 12345
    ss.erase(ss.begin()+24: 1234
    
    ss: 678910
    ss.erase(ss.begin()+2, ss.end()-1): 670
    
    ss: 678910
    ss.erase(3,3): 678
    Process returned 0 (0x0)   execution time : 0.018 s
    Press any key to continue.

#### 3.2 AC代码 ####

#include<vector>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n;
    vector<string> str;
    
    bool cmp(string a, string b) {
        
    	return a+b<b+a;
    }
    int main() {
        
    	cin>>n;
    	string s;
    	for(int i=0; i<n; i++){
        
    		cin>>s;
    		str.push_back(s);
    	}
    	sort(str.begin(), str.end(), cmp);
    
    	string ans;
    	for(int i=0; i<n; i++)
    		ans+=str[i];
    	while(ans.size() != 0 && ans[0] == '0')
    		ans.erase(ans.begin());
    
    	if(ans.size() == 0) cout << 0;
    	else cout << ans;
    
    	return 0;
    }

![在这里插入图片描述][79ce05b8dc7d4e2a890116fa15f591c9.png]

[_string_]: https://blog.csdn.net/qq_46371399/article/details/125870217?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166159716016782248593102%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=166159716016782248593102&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-125870217-null-null.nonecase&utm_term=STRING&spm=1018.2226.3001.4450
[79ce05b8dc7d4e2a890116fa15f591c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/09bc82d55b3b42c489246aa8687e4d07.png