csp信奥赛C++高频考点专项训练之贪心算法 --【排序贪心】：拼数

csp信奥赛C++高频考点专项训练之贪心算法 --【排序贪心】：拼数

题目描述

设有n nn个正整数a 1 … a n a_1 \dots a_na1​…an​，请将它们连接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数n nn。

第二行有n nn个整数，表示给出的n nn个整数a i a_iai​。

输出格式

一个正整数，表示最大的整数。

输入输出样例 1

输入 1

3 13 312 343

输出 1

34331213

输入输出样例 2

输入 2

4 7 13 4 246

输出 2

7424613

说明/提示

对于全部的测试点，保证1 ≤ n ≤ 20 1 \leq n \leq 201≤n≤20，1 ≤ a i ≤ 10 9 1 \leq a_i \leq 10^91≤ai​≤109。

思路分析

本题要求将若干个正整数拼接成一个最大的整数。不能直接按数值大小排序，因为需要考虑拼接后的字典序。例如9和89，"9"+"89" = "989"大于"89"+"9" = "899"，所以9应排在89前面。

正确做法：将所有数字转换为字符串，然后按照a + b > b + a的规则进行降序排序，最后依次拼接输出。此比较规则能保证任意两个字符串的拼接顺序最优，且满足传递性，因此排序后整体结果最大。

代码实现

#include<bits/stdc++.h>usingnamespacestd;// 比较函数：若 a+b > b+a 则 a 排在 b 前面boolcmp(string a,string b){returna+b>b+a;}intmain(){intn;cin>>n;vector<string>v(n);for(inti=0;i<n;++i){cin>>v[i];// 读入整数，作为字符串存储}sort(v.begin(),v.end(),cmp);// 按自定义规则排序for(string s:v){cout<<s;// 拼接输出}return0;}

功能分析

• 输入处理：读取整数个数n和n个正整数，存储为字符串向量。
• 排序规则：自定义比较函数cmp，判断a+b和b+a的字典序大小，确保排序后拼接结果最大。
• 输出结果：按排序后的顺序依次输出字符串，得到最大整数。
• 正确性：该贪心策略等价于求字符串连接后的最大字典序，已证明具有最优子结构和传递性，适用于本题数据范围（n ≤ 20，a i ≤ 10 9 a_i ≤ 10^9ai​≤109）。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}