分类练习题综合考试一
时量：4小时
1、出栈序列统计
【问题描述】
栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
【输入】
一个整数n(1<=n<=15)。
【输出】
一个整数，即可能输出序列的总数目。
【样例】
stack1.in
3
stack1.out
5
2、小木棍
【问题描述】
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
【输入】
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60，第二行为N 个用空格隔开的正整数，表示N根小木棍的长度。
【输出】
输出文件仅一行，表示要求的原始木棍的最小可能长度。
【样例】
stick.in
9
5 2 1 5 2 1 5 2 1
stick.out
6
3、书的复制
【问题描述】
现在要把m本有顺序的书分给k个人复制(抄写)，每一个人的抄写速度都一样，一本书不允许给两个(或以上)的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。【输入】
第一行两个整数m，k；(k<=m<=500)
第二行m个整数，第i个整数表示第i本书的页数。
【输出】
共k行，每行两个正整数，第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
【样例】
book.in
9 3
1 2 3 4 5 6 7 8 9
book.out
1 5
6 7
8 9
4、医院设置
【问题描述】
设有一棵二叉树，如图5-1：
其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个
结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1。
如上图中，若医院建在：
1处，则距离和=4+12+2*20+2*40=136
3处，则距离和=4*2+13+20+40=81
【输入】
第一行一个整数n，表示树的结点数。(n≤100)
接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格(一个或多个)分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。
【输出】
一个整数，表示最小距离和。
【样例】
hospital.in
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
hospital.out
81
5、马拉松接力赛
【问题描述】
某城市冬季举办环城25km马拉松接力赛，每个代表队有5人参加比赛，比赛要求每个队的每名参赛选手只能跑一次，一次至少跑1km、最多只能跑10km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。
刘老师作为学校代表队的教练，精心选择了5名长跑能手，进行了训练和测试，得到了这5名选手尽力连续跑1km、2km、…、10km的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完25km所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。
根据测试情况及一般运动员的情况得知，连续跑1km要比连续跑2km速度快、连续跑2km又要比连续跑3km速度快……也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。
【输入】
5行数据，分别是1到5号队员的测试数据，每行的10个整数，表示某一个运动员尽力连续跑1km、2km、…、101Km所用的时间。
【输出】
两行，第一行是最短的时间，第二行是五个数据，分别是1到5号队员各自连续跑的公里数。
【样例】
marath.in
333 700 1200 1710 2240 2613 3245 3956 4778 5899
300 610 960 1370 1800 2712 3834 4834 5998 7682 298 612 990 1560 2109 2896 3790 4747 5996 7654 289 577 890 1381 1976 2734 3876 5678 6890 9876 312 633 995 1467 1845 2634 3636 4812 5999 8123 marath.out
9748
6 5 5 4 5