首页 > 试题广场 >

Recover the Smallest Number (3

[编程题]Recover the Smallest Number (3

热度指数：2818 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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.

输入描述:

Each input file contains one test case.  Each case gives a positive integer N (<=10000) 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.

输出描述:

For each test case, print the smallest number in one line.  Do not output leading zeros.

示例1

输入

5 32 321 3214 0229 87

输出

22932132143287

算法知识视频讲解

C/C++

Myhui

#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
string s[10010];
bool cmp(string a,string b){
    return a+b<b+a;                   //string型直接拼接来比较
}
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>s[i];
    sort(s,s+n,cmp);
    string str;
    for(int i=0;i<n;i++)
        str+=s[i];                   //将排序后数字串拼接起来
    int len=str.length();
    int k;
    for(k=0;k<len;k++){
        if(str[k]!='0') break;      //找到第一个非0的数字
    }
    if(k==len) cout<<'0';           //若全为0，直接输出0
    else{
        for(;k<len;k++)
            cout<<str[k];
    }
    return 0;
}

编辑于 2018-01-28 02:34:23 回复(1)

算法妙妙屋

本文来自我的博客，http://blog.csdn.net/sinat_29278271，还有一些其他的pat题解，如果觉得本文有用不妨前去看看

最好和这道题一起看，觉得挺有意思UVA - 11729 Commando War

一道看起来很简单，写起来有点痛苦，最后解法比较有趣的题目。据说是一道面试题的改编。

题目给你一些数字的片段（number segments），所以应当用string存储而不是int,希望拼接之后能拼出的最小的数字，这是一道很神奇的题目，我分类讨论分了很多，最后突然发现它的最终解法无比简洁。

其实就是一个序的关系，所有的组合有n!种，（像"所谓组出最小数其实是获得字典序最小的拼接方式"这种废话我就不说了）。假设我们获得了其中的一个组合，然后又两个相邻的数字片段a,b。然后我们就要想，把a和b交换能不能使整个序列变小呢？这个问题的其实等价于b+a 是否小于a+b（此处"+"为连接符）,也就是说对于这样一个序列，如果某两个相邻的元素之间发生交换可以使得整个序列的值变小，我们就应该坚决的交换啊，所以这里定义一个新的序，用<<来表示，若a+b < b + a 则a应当在b前面，即a << b。然后呢，这种序是满足传递性的若a<<b ,b << c，则a<<c，所以迭代到最后，我们就会获得一个任何两个相邻元素都不能交换的局面，也就是所谓的答案。

这样一来我们的算法就有了，比较每两个相邻的元素，如果交换可以使得整个序列变大，就交换之，直到最后没有任何两个值之间能进行交换，啊，这不就是传说中的Bubble_Sort吗，真是一个令人激动的结论啊。对序列按照之前定义的序进行排序，如此就好了。

# include <cstdio>
# include <iostream>
# include <string>
using namespace std;

const int _size = 10000;
string num[_size];
bool cmp(const string& a,const string& b){return a + b< b + a;}
int main()
{
  int n,i;
  cin >> n;
  for (i=0;i<n;i++)
     cin >> num[i];
  sort(num,num+n,cmp);
  string out;
  for (i=0;i<n;i++)
      out += num[i];
  for (i=0;i<out.size()&&out[i]=='0';i++);
  if (i==out.size())
      printf("0");
  else 
      printf("%s",out.c_str()+i);
  printf("\n");
  return 0;
}

编辑于 2015-08-29 12:47:37 回复(2)

缘来有你201808241619550

from functools import cmp_to_key
def cmp(x,y):
    x=list(map(int,list(x)))
    y=list(map(int,list(y)))
    i=j=0
    while i<len(x) and j<len(y):
        if x[i]!=y[j]:
            return x[i]-y[j]
        i+=1
        j+=1
    if i==len(x) and j==len(y):
        return 0
    elif i==len(x):
        return x[0]-y[j]
    else:
        return x[i]-y[0]

segements=input().split()[1:]
segements.sort(key=cmp_to_key(cmp))

res="".join(segements)
for i in range(0,len(res)):
    if res[i]!="0":
        res=res[i:]
        break
if i==len(res)-1:
    res="0"
print(res)

发表于 2020-02-06 19:28:12 回复(0)

刘涛201801031713506

使用贪心算法，参考的别人的代码。

#include<iostream>

#include<string>

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;

int cmp(string a,string b)

{

return a+b<b+a;

}

int main()

{

vector<string> result;

int N;

cin>>N;

for(int i=0;i<N;i++)

{

string tmp;

cin>>tmp;

result.push_back(tmp);

}

sort(result.begin(),result.end(),cmp);

string s;

for(int i=0;i<N;i++)

{

s+=result[i];

}

while(s.length()!=0&&s[0]=='0')

{

s.erase(s.begin());

}

if(s.length()==0)

cout<<"0";

else

cout<<s;

cout<<endl;

return 0;

}

发表于 2018-03-07 15:44:56 回复(0)

袁博文202

from functools import cmp_to_key
cmp2key = cmp_to_key(lambda x,y: int(x+y)-int(y+x))
print(int(''.join(sorted(input().split()[1:],key=cmp2key))))

发表于 2018-05-03 15:14:09 回复(1)

猫猫猫1

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

bool cmp(string a,string b) {
	return a+b<b+a;
}

int main() {
    ios::sync_with_stdio(0);
	string s[10010];
	int n;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>s[i];
	}
	sort(s,s+n,cmp);
	string answer;
	for(int i=0; i<n; i++) {
		answer+=s[i];
	}
	while(answer[0]=='0'&&answer.size()!=0) {
		answer.erase(answer.begin());
	}
	if(answer.size()!=0){
		cout<<answer;
	}else{
		cout<<0;
	}
	return 0;
}

发表于 2022-11-12 10:24:52 回复(0)

刷牛客的三文鱼很爱吃肉

这道题的题干是否有瑕疵？“Notice that the first digit must not be zero.（第一个数字必须不为0）”，然而并没有说明如何处理全为0的用例（“1 000000”）。按照题意应该输出空串，然而答案给的是“0”，这显然不符合“第一个数字必须不为0”的条件。这里绝对是有坑的。

发表于 2021-03-09 16:50:26 回复(0)

咕噜咕噜_Official

冒泡排序的思路！冒泡排序永远的神！我永远爱冒泡排序！

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(string s1, string s2) {
    return s1 + s2 < s2 + s1;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N, total_size = 0;
    vector<string> buf;
    cin >> N;
    buf.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> buf[i];

    sort(buf.begin(), buf.end(), cmp);
    
    string str;
    for(int i = 0; i < buf.size(); i++)
        str += buf[i];
    
    int k;
    for(k = 0; k < str.size(); k++)
        if(str[k] != '0')
            break;
        
    if(k == str.size())
        cout << '0';
    else
        for(; k < str.size(); k++)
            cout << str[k];
        
    return 0;
}

发表于 2020-09-20 23:40:24 回复(0)

默默丶

//参照了上面有个大神的分享，他说的很详细，比喻成冒泡排序，对于任意两个a，b来说如果a+b<b+a
//那么肯定是a排在b前面，那么按照这种方式，每一次就会找一个最大的字符串排到最后面，这样就相当于冒泡排序了

#include<iostream>
(720)#include<vector>
#include<string>
(765)#include<algorithm>
using namespace std;
const int maxn = 10001;
bool cmp(string a, string b) {
	return a + b < b + a;
}
int main() {
	int n;
	cin >> n;
	string number[maxn];
	int visit[maxn] = { 0 };
	for (int i = 0; i < n; i++) {
		cin >> number[i];
	}
	sort(number, number + n, cmp);
	string answer = "";
	for (int i = 0; i < n; i++) {
		answer += number[i];
	}
	int j = 0;
	for (; j < answer.size(); j++) {
		if (answer[j] != '0') {
			break;
		}
	}
	if (j == answer.size()) {
		printf("0");
	}
	for (; j < answer.size(); j++) {
		printf("%c", answer[j]);
	}

}

发表于 2020-03-31 17:27:22 回复(0)

gangstar

#include
#include
#include
#include
using namespace std;
bool com(string a,string b) {//不能按照字典顺序从大到小排序，而是按照两个字符串拼接后的字典顺序排序的
    return a + b < b + a;
}
int main() {
    string str[10010],s;
    int n = 0,index = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }
    sort(str,str+n,com);
    for (int i = 0; i < n; i++)s += str[i];
    while (s.length() != 0&&s[0]=='0') {
        s.erase(s.begin());
    }
    if (s.length() == 0)cout << "0" << endl;
    else cout << s << endl;
    system("pause");
    return 0;
}

发表于 2019-10-13 19:11:01 回复(0)

小小呆萌坤

提供另外的一种算法,将每个字符串补全(长度为所有数据中的最长长度,用首字符来补) 之后按补全后结果从小到大排序连接即可.

例如 32-321-3214-0229-87

补全后 3233 - 3213 - 3214 - 0229 -8788

排序 0229 - 3213 - 3214 - 3233 - 8788

结果 0229 - 321 - 3214 -32 -87

合并 22932132143287

如果有反例请告诉我!谢谢

编辑于 2019-10-03 16:29:02 回复(2)

风蚀流云

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
string str[N];
bool cmp(string a, string b){
    return a+b<b+a;
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    string ans;
    cin>>n;
    for(int i = 0; i < n; i++) cin>>str[i];
    sort(str,str+n,cmp);
    for(int i = 0; i < n; i++) ans+=str[i];
    n = ans.length();
    int i = 0;
    while(i < n&&ans[i]=='0') i++;
    if(i==n) cout<<"0"<<endl;
    else cout<<ans.substr(i)<<endl;
    return 0;
}

编辑于 2019-05-05 08:07:28 回复(0)

Disconnect

from functools import cmp_to_key
def bikey(a,b):
    return int(a+b)-int(b+a)
lst = input().split()[1:]
lst.sort(key = cmp_to_key(bikey))
print(int(''.join(lst)))

发表于 2018-12-10 15:07:44 回复(0)

酒千觞

from functools import cmp_to_key
def cmp(a,b):
    a,b=int(a+b),int(b+a)
    return a-b
L=list(input().split()[1:])
L.sort(key=cmp_to_key(cmp))
for i in range(len(L)):
    if int(L[i])!=0:
        L[i]=str(int(L[i]))
        break
    else:
        L[i]=''
print(''.join(L) or '0')

发表于 2018-09-05 20:01:23 回复(0)

EricMaC

呵呵，我比较时是还判断了是否是前缀，看来不用

#include<stdio.h>

#include<vector>
#include<string>
#include<algorithm>
using namespace std;

vector<string> l;
bool isZero(string s){//是否全零
    for(int i=0;i<s.size();i++){
        if(s[i]!='0')
            return false;
    }
    return true;
}
bool cmp(string &s1,string &s2){
    if((s1.length()<s2.length()&&s2.find(s1)==0)||
        (s2.length()<s1.length()&&s1.find(s2)==0))//是前缀
        return s1+s2<s2+s1;//小的在前面
    else
        return s1<s2;
}
int main(){
    int n;
    scanf("%d",&n);

    char tmp[15];
    for(int i=0;i<n;i++){
        scanf("%s",tmp);
        if(isZero(tmp))//全零放开头，不考虑
            continue;
        l.push_back(string(tmp));
    }
    sort(l.begin(),l.end(),cmp);//字符串排序

    if(l.size()>0){
        int k=0;
        for(;k<l[0].size()&&l[0][k]=='0';k++)//去首位零
            ;
        l[0]=l[0].substr(k);
    }
    if(l.size()==0)//特判全0
        l.push_back("0");

    for(int i=0;i<l.size();i++){
        printf("%s",l[i].c_str());
    }
    return 0;
}

发表于 2018-08-26 11:44:42 回复(0)

C/C++

OFShare

//排序即可
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n;
string A[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>A[i];    
    sort(A+1,A+1+n,[](const string &x,const string &y){ return x+y<y+x;});
    string ans;int i=0;
    for(int i=1;i<=n;++i) ans+=A[i];
    while(ans[i]=='0'&&i<ans.size()-1) ++i;
    for(;i<ans.size();++i) cout<<ans[i];
    return 0; 
}

发表于 2018-03-18 00:38:30 回复(0)

C/C++

尼米茨的风

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 10010;
string str[maxn];

bool cmp(string a, string b){
    return a + b < b + a;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> str[i];
    }
    sort(str, str + n, 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;
}

发表于 2018-03-08 19:17:06 回复(0)

RicardoZi

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 10;
string num[maxn];

bool compare(string s1, string s2){
    string num1 = s1 + s2;
    string num2 = s2 + s1;
    return num1 < num2;
}

int main(){
    int n, pos = -1;
    cin >> n;
    string s;
    for(int i=0; i<n; i++)
        cin >> num[i];
    sort(num, num+n, compare);
    s = num[0];
    for(int i=1; i<n; i++)
        s = s + num[i];
    for(int i=0; i<s.size(); i++){
        if(s[i] != '0'){
            pos = i;
            break;
        }
    }
    if(pos == -1) cout << "0" << endl;
    else{
        string temp = s.substr(pos);
        cout << temp << endl;
    }
    return 0;
}

发表于 2017-09-05 21:16:38 回复(0)

loveISparadise

    #include<iostream>   
    #include<string>   
    #include<vector>   
    #include<algorithm>   
    using namespace std;   
    bool cmp(string a,string
      b){returna+b < b+a;}   
    intmain(){   
      intn,i;   
      cin >> n;   
      vector<string>
      data(n);   

        for(i=0;i<n;i++){cin >> data[i];}   

        sort(data.begin(),data.end(),cmp);   
      string result
      ="";   

        for(i=0;i<n;i++){result += data[i];}   

        for(i=0;i<result.size();i++){if(result[i] !='0'){break;}}   

        if(i==result.size()){i--;}   

        for(i;i<result.size();i++){cout << result[i];}   
      cout << endl;   
    }

        开始觉得很困难，后来发现发现可以分解成子问题，就是每次插一个字符串到结果里，对于结果里的字符串，要插入的字符串是在其前或后取决于

        a+b < b + a。突然灵光一闪，这不就是插入排序吗，然后猜测是直接根据这个判断排序即可。

      

        

      

发表于 2016-12-07 17:00:25 回复(0)

新世纪的神

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10005;
string num[maxn];
bool cmp(string a,string b){
    return a+b<b+a;
}
int main(){
    //freopen("in.txt","r",stdin);
    int n;
    string ans="";
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    sort(num,num+n,cmp);
    for(int i=0;i<n;i++){
        ans.append(num[i]);
    }
    int len=ans.length(),pos=-1;
    for(int i=0;i<len;i++){
        if(ans[i]!='0'){
            pos=i;
            break;
        }
    }
    if(pos<0){
        printf("0\n");
    }
    else{
        for(int i=pos;i<len;i++){
            printf("%c",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

发表于 2016-07-24 00:27:18 回复(0)