NC16783 [NOIP1998]拼数
2024-08-31 07:45:48
NC16783 [NOIP1998]拼数
题目
题目描述
设有 \(n\) 个正整数(\(n ≤ 20\)),将它们联接成一排,组成一个最大的多位整数。
例如:\(n=3\) 时,\(3\) 个整数 \(13\),\(312\) ,\(343\) 联接成的最大整数为:\(34331213\)
又如:$n=4 $ 时,\(4\) 个整数 \(7\) ,\(13\) ,\(4\) ,\(246\) 联接成的最大整数为:\(7424613\)
输入描述
第一行,一个正整数 \(n\) 。
第二行,\(n\) 个正整数。
输出描述
一个正整数,表示最大的整数
示例1
输入
3
13 312 343
输出
34331213
题解
思路
知识点:贪心,排序。
显然,根据字典序排列数字是最优的。但问题在于一些包含关系的数字是不符合的,如 \(989\) 和 \(9899\) 并不能单纯看字典序。
考虑看前后两者的和字符串的字典序排序,首先如果两者并不是包含关系,则这种排序不会因此改变;如果两者是包含关系可以用这种方法更进一步排序,注意这里传递性是要证明的,具体用数学归纳法即可。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
string str[27];
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);
for(int i = 0;i<n;i++){
cout<<str[i];
}
cout<<'\n';
return 0;
}
最新文章
- Linux tcpdump命令详解
- JavaScript中如何获取某年某月有多少天的问题
- 安装生物信息学软件-MetaPhlAn2
- 改变mvc web api 支持android ,ios ,ajax等方式跨域调用
- set_include_path — 设置 include_path 配置选项为当前脚本设置 include_path 运行时的配置选项。
- MongoDB 一对多关系建模
- com学习(一)GUID 和 接口
- 学渣告诉你,到底神马是傅里叶级数!转自 新浪@工程师style
- 在window server 2008 64位系统上 发布网站的过程中遇到的问题
- 使用EF实现数据库的增删改查
- [Java] HttpClient有个古怪的stalecheck选项
- 跨Storyboard调用
- Tenka1 Programmer Contest 2019
- netstat lsof ps 常用场景
- MyBatis探究-----动态SQL详解
- String为什么是不可变的?
- Spring日记_02之搭建一个新项目
- spring mvc 自动生成代码
- Bootstrap学习笔记-布局
- adb shell 运行时报错";adb server version (26) doesn&#39;t match this client (39); killing...";的解决方案