【题目描述】
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。
【输入描述】
数据的第 1 行是正整数 N，表示有 N 堆石子。
第 2 行有 N 个整数，第 i个整数ai表示第 i 堆石子的个数。
1≤N≤400，0≤ai≤20。
【输出描述】
输出共2行，第1 行为最小得分，第2 行为最大得分。
【样例输入】
4 4 5 9 4
【样例输出】
43 54
【题目描述】
在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
设计一个程序，计算出将N堆石子合并成一堆的最小得分。
【输入描述】
第一行为一个正整数N (2≤N≤100)；
以下N行,每行一个正整数，小于10000，分别表示第i堆石子的个数（1≤i≤N）。
【输出描述】
为一个正整数，即最小得分。
【样例输入】
7 13 7 8 16 21 4 18
【样例输出】
239
【题目描述】
给定n个闭区间[ai,bi]，其中i=1,2,...n。任意两个相邻或相交或相邻的闭区间可以合并为一个闭区间。例如，[1,2]和[2,3]可以合并为[1,3]。
[1,3]和[2,4]可以合并为[1,4]，但是[1,2]和[3,4]不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，则将这个闭区间输出，否则输出no
【输入描述】
第一行为一个整数n，3<n<50000。表示输入区间的数量。
之后n行，在第i行上（1<=i<=n）,为两个整数ai和bi，整数之间用一个空格分隔，表示区间[ai,bi]
(其中1<=ai<=bi<=10000)
【输出描述】
输出一行，如果这些区间最终可以合并为一个闭区间，输出这些闭区间的左右边界，用单个空格隔开；否则输出no
【样例输入】
5 5 6 1 5 10 10 6 9 8 10
【样例输出】
1 10
【题目描述】
设有N个选手进行循环比赛，其中 N=2^M ，要求每名选手要与其他的N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。
【输入描述】
输入M
【输出描述】
一个二维数组，表示比赛安排表，一行数据间用一个空格隔开。
【样例输入】
3
【样例输出】
1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1
一、基本思想
归并排序的核心思想是将两个已经有序的子序列合并成一个有序序列。整个过程分为两个主要步骤：
1.分解：将待排序的序列不断二分，直到每个子序列只包含一个元素（此时自然有序）
2.合并：将两个有序的子序列合并为一个有序序列
注意1：若将两个有序表合并成一个有序表，称为2-路归并。
注意2：归并排序则类似于二叉树的后序遍历：它会持续划分区间，直到区间内元素有序，然后利用额外空间对元素进行排序，并将它们合并回原区间，直至整个序列有序。这个过程中，划分区间相当于达到树的最底层，而归并排序则相当于从树的底层开始向上遍历。
二、算法步骤
1.分解阶段：
将长度为n的序列分成两个长度为n/2的子序列
递归地对这两个子序列进行归并排序
直到子序列长度为1（此时已经有序）
2.合并阶段：
申请空间，大小为两个已排序子序列之和
设定两个指针，分别指向两个子序列的起始位置
比较两个指针所指的元素，选择较小的放入合并空间，并移动指针到下一位置
重复上一步直到某一指针超出子序列范围
将另一子序列的剩余元素直接复制到合并序列的末尾
动图如下：
三、时间复杂度
最优情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)
归并排序的时间复杂度始终是O(n log n)，因为它总是将序列分成两半，需要进行log₂n次分解，每次合并操作的时间复杂度为O(n)。
四、空间复杂度
归并排序需要额外的空间来存储临时合并的数组，因此其空间复杂度为O(n)。
五、稳定性
归并排序是稳定的排序算法，因为在合并过程中，当两个元素相等时，可以保证左边的元素先被放入结果数组中。
六、优缺点
优点：
时间复杂度稳定为O(n log n)
适用于大规模数据排序
稳定排序算法
缺点：
需要额外的存储空间（非原地排序）
对于小规模数据排序效率可能不如简单排序算法
【题目描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴!因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则:
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱 wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱!
注意:比赛绝对不会让参赛者赔钱!
【输入描述】
第一行为 m，表示一开始奖励给每位参赛者的钱;第二行为n，表示有n个小游戏;
第三行有n个数，分别表示游戏1~n的规定完成期限;第四行有n个数，分别表示游戏1~n不能在规定期限前完成的扣款数
【输出描述】
仅1行。表示小伟能赢取最多的钱,
【样例输入】
10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10
【样例输出】
9950
【题目描述】
【输入描述】
【输出描述】
【样例输入】
3 0 2 2 4 1 3
【样例输出】
2
【题目描述】
同学们下课后去食堂，每个人都需要一段时间去点菜。
然而，某些同学点菜时间太长了。同学们对于等待很烦躁：他们希望，能尽量少的花时间等待。
(同学数<=100000)，(0<=点菜耗时<=10000)
他们希望在点菜时，能排成一个次序，使得总等待时间最短(即不包括点菜人的其他所有人的等待时间)。
【输入描述】
第一行是一个数字n，表示同学的个数
接下来n个数，表示点菜的耗时
【输出描述】
一个数，表示总等待时间。
【样例输入】
6 9 1 3 5 4 2
【样例输出】
35
【题目描述】
大战即将来临，杰洛特需要为自己增添战斗力，广袤的大陆有诸多豪杰，正好可以为杰洛特所用
杰洛特分别有两处地方n1,n2需要豪杰的战斗力
一共有n个豪杰，每一个豪杰拥有自己的战斗力pi,当然战斗力是越高越好，可是人人之间还是有差距的。
因此两个城池决定，各自选出最高战斗力的算术平均值之和。
【输入描述】
第一组一个n表示拥有多少个豪杰，以及一个n1,n2分别表示城池需要的豪杰数
接下来一行有n个数据分别表示各个豪杰的战斗力
【输出描述】
【样例输入】
4 1 2 1 2 3 4
【样例输出】
6.500000
【题目描述】
小蓝有一个字符串 s，他特别喜欢由以下三个字符组成的单词：l,q,b，任意顺序都可以，一共有 6 种可能：lqb、lbq、qlb、qbl、blq、bql。
现在他想从 s 中，尽可能切割出多个他喜欢的单词，请问最多能切割出多少个？单词指的是由若干个连续的字符组成的子字符串。
【输入描述】
输入一行包含一个字符串 s。
【输出描述】
输出一行包含一个整数表示答案。
【样例输入】
lqbblqblqlxqb
【样例输出】
3
【数据范围】
对于20%的数据，1<=|s|<=10
对于40%的数据，1<=|s|<=20
对于60%的数据，1<=|s|<=100
对于70%的数据，1<=|s|<=1000
对于80%的数据，1<=|s|<=10000
对于所有数据，1<=|s|<=10^5, s中只包含小写字母