題目

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(\le 10^4)$ 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

解題思路

　　題目大意： 給N個數(shù)字，然后組合成一個數(shù)字，求最小的組合。
　　解題思路： 這道題的關(guān)鍵在于，抽象出題目要求的排序規(guī)則，使用sort函數(shù)進(jìn)行排序。我們不妨從Demo中總結(jié)一下——
　　顯然，小的要放前面，0229比3214要小，比更短的87也更小，比其他都要小，所以放最前面。這一點(diǎn)符合string的operator<規(guī)則，可以直接使用a<b。
　　但是麻煩的是， 并不是所有的字符串都符合這個規(guī)則，其中，3214比32要大，但是如果把3214放在32前面，顯然不是正確的選擇——
　
　　但如果 （a+b）<（b+a）的組合成立的話 ，我們發(fā)現(xiàn)，這幾乎符合所有的條件，我們可以得到最小的排序組合。根據(jù)sort的排序規(guī)則，如果符合規(guī)則（a+b）<（b+a），那么a和b保持原來的順序，否則交換順序。
　　此外，測試數(shù)據(jù)存在邊界情況，第二個測試點(diǎn)，最大的數(shù)據(jù)可能是0，此時要輸出0。

/* ** @Brief:No.1038 of PAT advanced level. ** @Author:Jason.Lee ** @Date:2018-12-16 ** @status: Accepted! */ #include<iostream> #include<algorithm> #include<vector> #include<string> #include<sstream> using namespace std; int main(){int N;while(cin>>N){vector<string> segments;string temp;for(int i=0;i<N;i++){cin>>temp;segments.push_back(temp);}// 使用lambda表達(dá)式比定義cmp函數(shù)更簡潔sort(segments.begin(),segments.end(),[](string a,string b){return (a+b)<(b+a);});// 使用stringstream可以輕易的把string轉(zhuǎn)換成int型，//易于判斷string是否是零，以及消除首部多余的0stringstream strNum;int number;strNum<<segments[N-1];strNum>>number;if(number==0){cout<<0<<endl;continue;}strNum.clear();strNum<<segments[0];strNum>>number;cout<<number;for(int i=1;i<N;i++){cout<<segments[i];}cout<<endl;}return 0; }

總結(jié)

　　這道題有一種大道至簡、返璞歸真的感覺，最開始總結(jié)規(guī)律，搞得很復(fù)雜，把排序規(guī)則寫的很冗余，但是還是通過了，后來參考了別人的代碼，發(fā)現(xiàn)原來可以如此簡潔，看來總結(jié)抽象的能力還是不夠。發(fā)現(xiàn)了規(guī)律了之后，其實(shí)并不難。這道題我學(xué)到了——
　　1) 使用stringstream轉(zhuǎn)換string到int，更快捷高效；
　　2) 發(fā)現(xiàn)規(guī)律，抽象建模很重要，或許這就是我們常說的解決問題的能力。

總結(jié)

以上是生活随笔為你收集整理的1038 Recover the Smallest Number （30 分）-字符串分段排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。