首页 > 试题广场 >

Recover the Smallest Number (3

[编程题]Recover the Smallest Number (3
  • 热度指数：2870 时间限制：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头像 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头像 缘来有你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头像 刘涛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头像 袁博文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头像 猫猫猫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头像 咕噜咕噜_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)
Khirisma头像 Khirisma 
#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头像 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头像 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头像 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头像 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头像 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)
提交观点

问题信息

贪心 排序
难度：
20条回答 9562浏览

热门推荐

通过挑战的用户

相关试题

Recover the Smallest Number (30)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号