暂无测试数据。

排队接水(water)
【问题描述】
有n个人在一个水龙头前排队接水，假如每个人接水的时间为T i ，请编程找出这n个人排队的一种顺序，
使得n个人的平均等待时间最小。
【输入格式】
输入文件共两行，第一行为n；第二行分别表示第 1 个人到第n个人每人的接水时间T 1 ，T 2 ，…，T n ，每
个数据之间有 1 个空格。
【输出格式】
输出文件有两行，第一行为一种排队顺序，即 1 到 n 的一种排列；第二行为这种排列方案下的平均等
待时间(输出结果精确到小数点后两位)。
【输入输出样例】
water.in water.out
10 3 2 7 8 1 4 9 6 10 5
56 12 1 99 1000 234 33 55 99 812 532.00
2、最大整数（Noip1998 连接多位数）
【问题描述】
设有 n 个正整数（n≤20） ，将它们联接成一排，组成一个最大的多位整数。
例如：n=3 时，3 个整数 13，312，343 联接成的最大整数为：34331213
又如：n=4 时，4 个整数 7，13，4，246 联接成的最大整数为：7424613
【输入格式】
n
n 个数
【输出格式】
联接成的多位数
【输入样例】
3
13 312 343
【输出样例】
34331213
3、纪念品分组(NOIP2007)
【题目描述】
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念
品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪
念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的
数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
【输入格式】
输入文件 group.in 包含 n +2 行：
第 1 行包括一个整数 w ，为每组纪念品价格之和的上限。
第 2 行为一个整数 n ，表示购来的纪念品的总件数。
第 3~ n +2 行每行包含一个正整数 p i (5 <= p i <= w )，表示所对应纪念品的价格。
【输出格式】
输出文件 group.out 仅一行，包含一个整数，即最少的分组数目。
【输入输出样例】
group.in group.out
100
9
90
20
20
30
50
60
70
80
90
6
【限制】
50%的数据满足：1 <= n <= 15
100%的数据满足：1 <= n <= 30000, 80 <= w <= 200
4、合并果子(Noip2004)
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定
把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所
有的果子经过 n-1 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体
力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重
量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的
体力最少，并输出这个最小的体力耗费值。
例如有 3 种果子，数目依次为 1，2，9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。接着，
将新堆与原先的第三堆合并， 又得到新的堆， 数目为 12， 耗费体力为 12。 所以多多总共耗费体力=3+12=15。
可以证明 15 为最小的体力耗费值。
【输入文件】
输入文件 fruit.in包括两行，第一行是一个整数n（1 <= n <= 10000） ，表示果子的种类数。第二行
包含n个整数，用空格分隔，第i个整数a i （1 <= a i <= 20000）是第i种果子的数目。
【输出文件】
输出文件 fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这
个值小于 2
31 。
【样例输入】
3
1 2 9
【样例输出】
15
【数据规模】
对于 30%的数据，保证有 n <= 1000；
对于 50%的数据，保证有 n <= 5000；
对于全部的数据，保证有 n <= 10000。
5、美元汇率（dollars）
【问题描述】
在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，
使他从 100 美元开始，最后能获得最高可能的价值。
【输入格式】
输入文件的第一行是一个自然数 N，1≤N≤100，表示戴维学习汇率的天数。
接下来的 N 行中每行是一个自然数 A，1≤A≤1000。第 i+1 行的 A 表示预先知道的第 i+1 天的平均汇
率，在这一天中，戴维既能用 100 美元买 A 马克也能用 A 马克购买 100 美元。
【输出格式】
输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。
注意：考虑到实数算术运算中进位的误差，结果在正确结果 0.05 美元范围内的被认为是正确的，戴维
必须在最后一天结束之前将他的钱都换成美元。
【输入样例】
5
400
300
500
300
250
【输出样例】
266.66
样例解释 (无需输出)
Day 1 ... changing 100.0000 美元= 400.0000 马克
Day 2 ... changing 400.0000 马克= 133.3333 美元
Day 3 ... changing 133.3333 美元= 666.6666 马克
Day 5 ... changing 666.6666 马克= 266.6666 美元
6、零件分组(stick)
【 问题描述】
某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi） 。现在为了加工需要，要将
它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若 i<j，则 Li<=Lj，Wi<=Wj）的序
列。请问至少要分成几组?
【输入格式】
第一行为一个整数 N（N<=1000） ，表示零件的个数。第二行有 N 对正整数，每对正整数表示这些零件
的长度和重量，长度和重量均不超过 10000。
【输出格式】
仅一行，即最少分成的组数。
【输入样例】
5
8 4 3 8 2 3 9 7 3 5
【输出样例】
2
7 、运输(trans)
【问题描述】
现在已知 N 件商品。和搬运它们其中每一件的费用。现在搬家公司的老板 Mr.B 决定让
我们每次任意选取 2 件商品。 然后这 2 件商品只算一件商品的费用。 但是这个商品的搬运费
用是将选出的 2 个商品的费用之和除以 K 的运算结果。如此反复。直到只收一件商品的钱。
这个就是商店要付的费用。想尽可能的少付钱，以便将更多的钱卷给希望工程。所以请你帮
他计算一下最少只用付多少钱。
【输入格式】
n,k
w1,w2,…,wn（每一件商品的搬运费用）
【输出格式】
输出一个数字，表示最少付多少钱。
【输入样例】
5 2
1 2 3 4 5
【输出样例】
1
【数据规模】
n<=10000
k<=10000
8 、最佳游览线路(Noi1994)
某旅游区的街道成网格状。其中东西向的街道都是旅游街，南北向的街道都是林荫道。
由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既
可从南向北走，也可以从北向南走。
阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻
两个路口之间的街道值得游览的程度，分值时从-100 到 100 的整数，所有林阴道不打分。
所有分值不可能全是负分。
例如图是被打过分的某旅游区的街道图：
阿龙可以从任一个路口开始游览，在任一个路口结束游览。请你写一个程序，帮助阿龙
找一条最佳的游览线路，使得这条线路的所有分值总和最大。
【输入格式】
第一行是两个整数 M 和 N，之间用一个空格符隔开，M 表示有多少条旅游街（1≦M≦
100） ，N 表示有多少条林阴道（1≦M≦20001） 。接下来的 M 行依次给出了由北向南每条旅
游街的分值信息。每行有 N-1 个整数，依次表示了自西向东旅游街每一小段的分值。同一
行相邻两个数之间用一个空格隔开。
【输出格式】
只有一行，是一个整数，表示你的程序找到的最佳游览线路的总分值。
【输入输出样例】
travel.in travel.out
3 6
-50 –47 36 –30 –23
17 –19 –34 –13 –8
-42 –3 –43 34 –45
84
9 、营养膳食(diet)
【问题描述】
阿月正在女朋友宁宁的监督下完成自己的增肥计划。
为了增肥，阿月希望吃到更多的脂肪。然而也不能只吃高脂肪食品，那样的话就会导致
缺少其他营养。 阿月通过研究发现： 真正的营养膳食规定某类食品不宜一次性吃超过若干份。
比如就一顿饭来说，肉类不宜吃超过 1 份，鱼类不宜吃超过 1 份，蛋类不宜吃超过 1 份，蔬
菜类不宜吃超过 2 份。 阿月想要在营养膳食的情况下吃到更多的脂肪， 当然阿月的食量也是
有限的。
【输入格式】
第一行包含三个正整数 n（n≤200）,m（m≤100）和 k（k≤100） 。表示阿月每顿饭最
多可以吃 m 份食品，同时有 n 种食品供阿月选择，而这 n 种食品分为 k 类。第二行包含 k
个不超过 10 的正整数，表示可以吃 1 到 k 类食品的最大份数。接下来 n 行每行包括 2 个正
整数，分别表示该食品的脂肪指数 ai 和所属的类别 bi，其中 ai≤100，bi≤k。
【输出格式】
一个数字即阿月可以吃到的最大脂肪指数和。
【样例输入】
6 6 3
3 3 2
15 1
15 2
10 2
15 2
10 2
5 3
【样例输出】
60