p1012 [noip1998 提高组] 拼数

题目描述

给定 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，将它们联接成一排，组成一个最大的多位整数。

例如： $n=3$， $a_1=3$， $a_2=32$， $a_3=321$，则可以联接成的最大整数为 $332321$。

输入格式

第一行输入一个正整数 $n$，表示正整数的个数。

第二行输入 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示给定的正整数。

输出格式

输出联接成的最大整数。

数据范围

$1\leq n\leq 100$

输入样例

3
3 32 321

输出样例

332321

算法1

(字符串排序) $O(nlogn)$

1.将所有数字转化为字符串
2.将字符串按照特定规则排序
3.将排序后的字符串拼接起来

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

p1011 [noip1998 提高组] 车站

题目描述：

有一个车站，有n个人要上车，但是车只有m个座位，所以只有前m个人能够上车，后面的人只能等下一班车。现在有k辆车，每辆车的座位数也是m个，问最少需要多少时间才能让所有人都上车？

输入格式：

输入共k+1行，第一行包含三个整数n,m,k，分别表示总人数，每辆车的座位数，以及车的数量。

接下来k行，每行包含m个整数，表示每辆车上的人的编号，编号从1开始。

输出格式：

输出一个整数，表示最少需要的时间。

输入样例：

10 3 3
1 2 3
4 5 6
7 8 9
10

输出样例：

4

算法1

(贪心) $O(n)$

每辆车都坐满，这样可以保证最少的车次数。

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

p1025 [noip2001 提高组] 数的划分

题目描述

将正整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5；

1，5，1；

5，1，1。

输入格式

两个正整数n，k，中间用空格隔开。

输出格式

输出划分方案的总数。

数据范围

1≤n≤200，1≤k≤n。

输入样例

7 3

输出样例

4

算法1

(递归) $O(n^2)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码