【PAT】【Advanced Level】1038. Recover the Smallest Number (30)

2024-06-17 04:32

本文主要是介绍【PAT】【Advanced Level】1038. Recover the Smallest Number (30),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1038. Recover the Smallest Number (30)

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

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 (<=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.

Output Specification:

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

Sample Input:
5 32 321 3214 0229 87
Sample Output:
22932132143287
原题链接:

https://www.patest.cn/contests/pat-a-practise/1038

https://www.nowcoder.com/questionTerminal/05c37a5c79964945930f526c75c87ba5

思路:

首先想到的是直接排序输出

得9分

后来参考牛客网上Uncle_Sugar的题解:

链接:https://www.nowcoder.com/questionTerminal/05c37a5c79964945930f526c75c87ba5
来源:牛客网

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


CODE:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
string ch[100000];
/*
bool cmp(char* a,char* b)
{return strcmp(a,b)<0;
}
*/
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>>ch[i];//scanf("%s",&ch[i]);//cout<<ch[i]<<endl;}sort(ch,ch+n,cmp);int st=0;while (atoi(ch[st].c_str())==0){st++;if(st>=n)break;}if (st==n){cout<<0<<endl;}else{printf("%d",atoi(ch[st].c_str()));st++;for (int i=st;i<n;i++)printf("%s",ch[i].c_str());}return 0;
}



这篇关于【PAT】【Advanced Level】1038. Recover the Smallest Number (30)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1068479

相关文章

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

30常用 Maven 命令

Maven 是一个强大的项目管理和构建工具,它广泛用于 Java 项目的依赖管理、构建流程和插件集成。Maven 的命令行工具提供了大量的命令来帮助开发人员管理项目的生命周期、依赖和插件。以下是 常用 Maven 命令的使用场景及其详细解释。 1. mvn clean 使用场景:清理项目的生成目录,通常用于删除项目中自动生成的文件(如 target/ 目录)。共性规律:清理操作

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

c++习题30-求10000以内N的阶乘

目录 一,题目  二,思路 三,代码    一,题目  描述 求10000以内n的阶乘。 输入描述 只有一行输入,整数n(0≤n≤10000)。 输出描述 一行,即n!的值。 用例输入 1  4 用例输出 1  24   二,思路 n    n!           0    1 1    1*1=1 2    1*2=2 3    2*3=6 4

Jenkins 通过 Version Number Plugin 自动生成和管理构建的版本号

步骤 1:安装 Version Number Plugin 登录 Jenkins 的管理界面。进入 “Manage Jenkins” -> “Manage Plugins”。在 “Available” 选项卡中搜索 “Version Number Plugin”。选中并安装插件,完成后可能需要重启 Jenkins。 步骤 2:配置版本号生成 打开项目配置页面。在下方找到 “Build Env

nyoj 1038 纸牌游戏

poj 的一道改编题,说是翻译题更恰当,因为只是小幅度改动。 一道模拟题,代码掌控能力比较好,思维逻辑清晰的话就能AC。 代码如下: #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{char c[5];int rk;char da[5];int nu

嵌入式面试经典30问:二

1. 嵌入式系统中,如何选择合适的微控制器或微处理器? 在嵌入式系统中选择合适的微控制器(MCU)或微处理器(MPU)时,需要考虑多个因素以确保所选组件能够满足项目的具体需求。以下是一些关键步骤和考虑因素: 1.1 确定项目需求 性能要求:根据项目的复杂度、处理速度和数据吞吐量等要求,确定所需的处理器性能。功耗:评估系统的功耗需求,选择低功耗的MCU或MPU以延长电池寿命或减少能源消耗。成本

MiniCPM-V: A GPT-4V Level MLLM on Your Phone

MiniCPM-V: A GPT-4V Level MLLM on Your Phone 研究背景和动机 现有的MLLM通常需要大量的参数和计算资源,限制了其在实际应用中的范围。大部分MLLM需要部署在高性能云服务器上,这种高成本和高能耗的特点,阻碍了其在移动设备、离线和隐私保护场景中的应用。 文章主要贡献: 提出了MiniCPM-V系列模型,能在移动端设备上部署的MLLM。 性能优越:

【全网最全】2024年数学建模国赛A题30页完整建模文档+17页成品论文+保奖matla代码+可视化图表等(后续会更新)

您的点赞收藏是我继续更新的最大动力! 一定要点击如下的卡片,那是获取资料的入口! 【全网最全】2024年数学建模国赛A题30页完整建模文档+17页成品论文+保奖matla代码+可视化图表等(后续会更新)「首先来看看目前已有的资料,还会不断更新哦~一次购买,后续不会再被收费哦,保证是全网最全资源,随着后续内容更新,价格会上涨,越早购买,价格越低,让大家再也不需要到处买断片资料啦~💰💸👋」�