蓝桥杯2582证整数拼接
时间: 2024-06-05 10:06:21 浏览: 18
题目描述
给定 $n$ 个正整数 $a_1,a_2,\cdots,a_n$,将它们拼接成一些数,使得拼接后的每个数都是正整数,并且这些数的和最小。
例如,当 $n=4$,$a_1=1,a_2=5,a_3=2,a_4=4$ 时,拼接后的 $3$ 个数 $125,4,1$ 的和最小,为 $130$。
输入格式
第一行包含一个整数 $n$,表示给定正整数的个数。
第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。
输出格式
输出一个整数,表示最小的和。
数据范围
$1\leq n\leq 10^3$
$1\leq a_i\leq 10^4$
输入样例1:
4
1 5 2 4
输出样例1:
130
输入样例2:
2
14 23
输出样例2:
374
算法1
(贪心) $O(nlogn)$
先将所有数转化为字符串,然后比较两个数拼接后的大小,从小到大排序,然后依次拼接即可。
时间复杂度
排序的时间复杂度是 $O(nlogn)$,拼接的时间复杂度是 $O(n)$,因此总时间复杂度为 $O(nlogn)$。
C++ 代码
算法2
(动态规划) $O(n^2)$
维护一个数组 $dp[i]$ 表示从前 $i$ 个数中选取一些数拼接成的数的最小值,初始值 $dp[0]=0$。
对于每个 $dp[i]$,枚举它之前的所有 $dp[j]$,$j<i$,将 $a_{j+1}$ 到 $a_i$ 这些数拼接成一个数,将其加到 $dp[j]$ 上,更新 $dp[i]$ 的最小值。
最终 $dp[n]$ 就是答案。
时间复杂度
状态总共有 $n$ 个,对于每个状态,需要枚举前面的所有状态,因此总时间复杂度为 $O(n^2)$。
C++ 代码
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)