PAT 1038 Recover the Smallest Number[dp][难]
1038 Recover the Smallest Number (30 分)
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
题目大意:给出几个数,要求求出它们的片段拼接,并且这个数是所有数中最小的。
//一看到就不太明白怎么做,拼接不同总长度也不一定相同,有0开头的,如果放在中间的话就算是中间一位了。没什么思路,考试遇到这个的话会跪。
代码来自:https://www.liuchuo.net/archives/2303
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp0(string a, string b) {//两个相同的数相加,它们的长度肯定是相同的。
return a + b < b + a;
}
string str[];//使用字符串数组!
int main() {
int n;
scanf("%d", &n);
for(int i = ; i < n; i++)
cin >> str[i];//以String作为输入。
sort(str, str + n, cmp0);
string s;
for(int i = ; i < n; i++)
s += str[i];//将字符串拼接。
while(s.length() != && s[] == '')
s.erase(s.begin());//将开头的0除去。
if(s.length() == ) cout << ;
cout << s;
return ;
}
//柳神的代码简直叹为观止。厉害了,学习了。
1.对字符串的处理,关键是这个cmp0函数的使用。
最新文章
- vaadin学习,重要的网址
- MongoDB分片(sharding)
- 《你必须知道的.NET》读书笔记:方法表初窥
- TCP 连接中断的判断
- WPF视频教程系列笔记
- drop.delete.trauncat的区别
- javax.servlet.ServletException: Servlet execution threw an exception 异常解决之一
- mysql中select distinct的用法
- 王立平--Unity综上所述控制
- Debian系统简要说明
- net core 程序docker打包镜像并发布到官方store
- css基础语法三
- QQ小橙团队排表机器人使用方法
- excel数据有隐藏字符导致正则校验不通过
- Codeforces Round #481 (Div. 3)
- Python3学习之路~5.7 Json &; pickle 模块
- WordDenified.exportedUI
- python2和Python3异同总结
- XtrasReport 标签打印
- java结构
热门文章
- 实践jQuery Easyui后本地化有感
- C++ 类中的const关键字
- imx6 uboot splash image
- Cloudera公司主要提供Apache Hadoop开发工程师认证
- IoC是一个很大的概念,可以用不同的方式实现。其主要形式有两种:
- Request获取具有相同 name 属性表单元素值
- error: Please reinstall the libcurl distribution - easy.h should be in &;lt;curl-dir&;gt;/include/curl/
- Android解析JSON速度对比
- 部分常用dos命令
- 【BZOJ3425】Poi2013 Polarization 猜结论+DP