<
，这是的和为total1，而把ki和kj互换位置，设新的和为total2，则：
我们发现上述△total恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。
从而证明了我们的设想。
既然如此，我们就得到了一种最有贪心策略：
把接水时间少的人尽可能排在前面。
这样一样，问题的本质就变成：
把n个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。
3.2智力大冲浪
源程序名riddle.?
?
?
（pas,c,cpp）
可执行文件名riddle.exe
输入文件名riddle.in
输出文件名riddle.out
【问题描述】
小伟报名参加中央电视台的智力大冲浪节目。
本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。
先不要太高兴！
因为这些钱还不一定都是你的？
！
接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段（n≤500），它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成（1≤ti≤n）。
如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。
当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。
主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。
作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！
注意：
比赛绝对不会让参赛者赔钱!
【输入】
输入文件riddle.in，共4行。
第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
【输出】
输出文件riddle.out，仅1行。
表示小伟能赢取最多的钱。
【样例】
riddle.inriddle.out
100009950
7
4243146
70605040302010
【算法分析】
因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。
贪心的主要思想是要让扣款数值大的尽量准时完成。
这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。
假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢?
应该放在第k个时段，因为放在1～k任意一个位置，效果都是一样的。
一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请看下面的参考程序1。
本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。
当扫描到第n个时段，发现里面所分配的任务的结束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1～n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序2。
3.3取火柴游戏
源程序名match.?
?
?
（pas,c,cpp）
可执行文件名match.exe
输入文件名match.in
输出文件名match.out
【问题描述】
输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。
取的规则如下：
每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。
谁取走最后一根火柴为胜利者。
例如：
k＝2，n1＝n2＝2，A代表你，P代表计算机，若决定A先取：
A：
（2,2）→（1,2）{从一堆中取一根}
P：
（1,2）→（1,1）{从另一堆中取一根}
A：
（1,1）→（1,0）
P：
（1,0）→（0,0）{P胜利}
如果决定A后取：
P：
（2,2）→（2,0）
A：
（2,0）→0,0）{A胜利}
又如k＝3，n1=1，n2＝2，n3＝3，A决定后取：
P：
（1,2,3）→（0,2,3）
A：
（0,2,3）→（0,2,2）
A已将游戏归结为（2,2）的情况，不管P如何取A都必胜。
编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输
出第一次该如何取。
如果是先取必败，则输出“lose”。
【样例1】
match.inmatch.out
343{表示第一次从第3堆取4个出来，必胜}
369365{第一次取后的状态}
【样例2】
match.inmatch.out
4lose{先取必败}
15221910
【算法分析】
从问题的描述分析，可以将问题中的k堆火柴棒抽象为k个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为0时，游戏结束，最后—次取火柴棒的人为胜方。
当k较小，且k堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态（全零）反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。
但当k和ni都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于n个非负整数的奇偶状态的定义：
如果把n个非负整数都化成二进制数，然后对n个二进制数按位相加（不进行进位），若每一位相加的结果都为偶数，则称这n个非负整数的状态为偶状态，否则称之为奇状态。
可以证明：
任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。
前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变。
这一位的改变就破坏了原来的偶状态。
后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第k位，则n个数的对应的二进制数中至少存在一个数，其第k位为1，将这个二进制数的第k位变成0，则所有二进制数的第k位上的数字之和就变成了偶数。
然后再对这个数的比k位低的所有位作如下调整：
如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为0，则改为1，若原来的值为1，则改为0，这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从1变成了0。
如n＝3时，三堆火柴棒的数量分别为3，6，9，则3＝（0011）2，6＝（0110）2，9＝（1001）2，最高位之和为1，其中9对应的二进制数的最高位为1，将其变为0，次高位之和也是1，9对应的二进制数的次高位为0，根据证明过程将其变为1，最后二位数字之和均为偶数，无需作任何改变，这样9＝（1001）2被变成了（0101）2=5，显然，3=（0011）2，6=（0110）2，5=（0101）2是一个偶状态。
有了前面的分析，一种贪心算法就出来了。
程序中用n个包含16个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如b[i,0]存放第i个数的最低位，n个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用0和1来表示，0表示偶，1表示奇。
最后的状态（全0）为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。
反之则先取必胜。
【后记】
大家都知道国际象棋特级大师卡斯帕罗夫与IBM公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧!
有了以上算法后，我们也可以编写出这样一个游戏程序。
让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。
3.4加工生产调度
源程序名prod.?
?
?
（pas,c,cpp）
可执行文件名prod.exe
输入文件名prod.in
输出文件名prod.out
【问题描述】
某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。
某个产品i在A、B两车间加工的时间分别为Ai、Bi。
怎样安排这n个产品的加工顺序，才能使总的加工时间最短。
这里所说的加工时间是指：
从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
【输入】
第一行仅—个数据n（0接下来n个数据是表示这n个产品在A车间加工各自所要的时间（都是整数）。
最后的n个数据是表示这n个产品在B车间加工各自所要的时间（都是整数）。
【输出】
第一行一个数据，表示最少的加工时间；
第二行是一种最小加工时间的加工顺序。
【样例】
prod.in
5
358710
62149
prod.out
34
15423
【算法分析】
本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。
一旦A车间开始加工，便会不停地进行加工（我们不要去管车间是否能够一直生产，因为他们有三班，可以24时间不停地运转）。
关键是B车间在生产的过程中，有可能要等待A车间的初加工产品。
很显然所安排的第一个产品在A车间加工时，B车间是要等待的，最后一个产品在B车间加工时，A车间已经完成了任务。
要使总的空闲时间最少，就要把在A车间加工时间最短的部件优先加工，这样使得B车间能以最快的速度开始加工；把放在B车间加工时间最短的产品放在最后加工，这样使得最后A车间的空闲时间最少。
设计出这样的贪心法：
设Mi＝min{Ai，Bi}
将M按照由小到大的顺序排序，然后从第一个开始处理，如果Mi=Ai，则将它安排在从头开始的已经安排的生产顺序后面，如果Mi＝Bi，则将它安排在从尾开始的已安排的生产顺序前面。
这种安排是否是最少的加工时间，还要通过数学证明。
证明如下：
设S＝在这样的条件下，加工S中任务所要的最短时间T（S,t）=min{Ai+T（s-{Ji}，Bi+max{t-Ai,0}）}，其中，Ji∈S。
图3-1是加工作业i时A车间等待B车间的情况：
图3-1A等B的情况
图3-2是加工作业i时B车间等待A车间的情形：
图3-2B等A的情况
假设最佳的方案中，先加工作业Ji，然后再加工作业Jj，则有：
如果
，则
如果
，则
如果
，则
如果将作业Ji和作业Jj的加工顺序调整，则有：
其中，
按照上面的假设，有T<=T’，所以有：
从而有：
即：
这说是所谓的Johnson公式，也就是说在此公式成立的条件下，优先安排任务Ji在Jj之前可以得到最优解。
也就是在A车间加工时间短的安排在前面，在B车间加工时间短的任务安排在后面。
以样例数据为例：
（A1,A2,A3,A4,A5）=（3,5,8,7,10）
（B1,B2,B3,B4,B5）=（6,2,1,4,9）
则（m1,m2,m3,m4,m5）=（3,2,1,4,9）
排序之后为：
（m3,m2,m1,m4,m5）
处理m3，因为m3=B3，所以m3安排在后面（，，，，3）；
处理m2，因为m2=B2，所以m2安排在后面（，，，2，3）；
处理m1，因为m1=A1，所以m1安排在前面（1，，，2，3）；
处理m4，因为m4=B4，所以m4安排在后面（1，，4，2，3）；
处理m5，因为m5=B5，所以m5安排在后面（1，5，4，2，3）。
从而得到加工的顺序1，5，4，2，3。
计算出最短的加工时间34。
【补充说明】
由于本题的原始数据并没有保证数据间没有重复，所以在数据有重复的情况下生产调度安排并不是惟一的。
但是最少的加工时间是惟一的。
3.5最大乘积
源程序名maxmul.?
?
?
（pas,c,cpp）
可执行文件名maxmul.exe
输入文件名maxmul.in
输出文件名maxmul.out
【问题描述】
一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。
现在你的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
【输入】
只一个正整数n，（3≤n≤10000）。
【输出】
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
【样例】
maxmul.inmaxmul.out
10235
30
【算法分析】
初看此题，很容易想到用回溯法进行搜索，但是这里的n范围比较大，最多到10000，如果盲目搜索，运行时间比较长，效率很低，对于部分数据可能得到结果，对于大部分数据会超时或栈溢出。
先来看看几个n比较小的例子，看能否从中找出规律：
n
分解方案
最大的乘积
5
23
6
6
24
8
7
34
12
8
35
15
9
234
24
10
235
30
可以发现，将n分解成a1,a2,a3,a4,…,am这m个自然数，该序列为从2开始的一串由小到大的自然数，如果a1为1，则对乘积没有影响，而且使n减少，没有实际意义，只有特殊情况如n为3、4时才可能用上。
设h>＝5，可以证明当将h拆分为两个不相同的部分并且两部分都大于1时两部分的乘积大于h。
证明如下：
将h分为两部分：
a，h-a其中2<＝aa*（h-a）-h＝h*a-a*a-h＝h*（a-1）-a*a
因为h>2*a，所以a*（h-a）-h>2*a*（a-1）-a*a=a*a-2*a=a*（a-2）
又因为a>＝2，所以a*（a-2）>=0，所以a*（h-a）-h>O即a*（h-a）>h。
从上面的证明可以看出，对于指定的正整数，如果其大于等于5，将它拆分为不同的部分后乘积变大，对于中间结果也是如此。
因此可以将指定的n，依次拆成a1+a2+a3+a4+…+am，乘积最大。
现在的问题是如何拆分才能保证n＝a1+a2+a3+a4+…+am呢?
可以先这样取：
当和不足n时，a1取2，a2取3，…，am-1取m，即从2开始按照自然数的顺序取数，最后剩余的数给am，如果am<=am-1，此时am跟前面的数字出现了重复，则把am从后面开始平均分布给前面的m-1个数。
为什么要从后面开始往前呢?
同样是考虑数据不出现重复的问题，如果是从前面往后面来平均分配，如2加上1以后变成3，就跟后面的已有的3出现了重复。
这样操作到底是否正确、是否能保证乘积最大呢?
还要加以证明。
证明过程如下：
设两个整数a，b的和为2s，且a<>b，设a＝s-1，则b＝s+1，a*b=（s-1）*（s+1）=s2-1，如果a=s-2，则b＝s+2，a*b＝（s-2）*（s+2）＝s2-4。
a-b的绝对值越小，乘积的常数项越大，即乘积越大，上面的序列a1,a2,a3,a4,…,am正好满足了a-b的绝对值最小。
但是还要注意两个特例就是n=3和n=4的情况，它们的分解方案分别为1，2和1，3，乘积分别为2和3。
以n=10为例，先拆分为：
10=2+3+4+1，最后一项为1，比4小，将其分配给前面的一项，得到10=2+3+5，所以最大的乘积为2*3*5＝30。
以n=20为例，拆分为：
20=2+3+4+5+6，正好是连续自然数的和，所以最大乘积为2*3*4*5*6=720。
再以n=26为例，先拆分为：
26=2+3+4+5+6+6，因为最后一项为6，不比最后第二项大，所以将其平均分给前面的项，优先考虑后面的项，即前面的4项各分到1，笫5项6分到2，最后是26＝3+4+5+6+8，所以最大的乘积为3*4*5*6*8＝2880。
由于n可能大到10000，分解之后的各项乘积位数比较多，超过普通的数据类型的位数，所以要用到高精度运算来进行整数的乘法运算，将结果保存在数组里。
本题的贪心策略就是：
要使乘积最大，尽可能地将指定的n（n>4）拆分成从2开始的连续的自然数的和，如果最后有剩余的数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。
基本算法描述如下：
（1）拆分过程
拆分的数a先取2；
当n>a时做
Begin
选择a作为一项；
a增加1；
n减少a；
End；
如果n>0，那么将n从最后一项开始平均分给各项；
如果n还大于0，再从最后一项开始分一次；
（2）求乘积
设置一个数组来存放乘积，初始状态位数为1，结果为1；
将上面拆分的各项依次跟数组各项相乘并考虑进位；
3.6种树
源程序名trees.?
?
?
（pas,c,cpp）
可执行文件名trees.exe
输入文件名trees.in
输出文件名trees.out
【问题描述】
一条街的一边有几座房子。
因为环保原因居民想要在路边种些树。
路边的地区被分割成块，并被编号成1..N。
每个部分为一个单位尺寸大小并最多可种一棵树。
每个居民想在门前种些树并指定了三个号码B，E，T。
这三个数表示该居民想在B和E之间最少种T棵树。
当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。
居民们想种树的各自区域可以交叉。
你的任务是求出能满足所有要求的最少的树的数量。
写一个程序完成以下工作：
*从trees.in读入数据
*计算最少要种树的数量和位置
*把结果写到trees.out
【输入】
第一行包含数据N，区域的个数（0第二行包含H，房子的数目（0下面的H行描述居民们的需要：
BET，0【输出】
输出文件第一行写有树的数目，下面的行包括所有树的位置，相邻两数之间用一个空格隔开。
【样例】
trees.intrees.out
95
414589
142
462
892
352
【算法分析】
不难想到下面的贪心算法：
按照每个区间的右端点排序，从左向右扫描，把每个区间内的树都尽量种在该区间的右端，由于后一个区间的右端不在这个区间的右端的左边（排序），可以保证这些树尽可能多地被下面的区间利用到。
扫描需要的时间为O（h），更新需要的时间为O（n），所以总的时间复杂度为O（n*h）。
3.7餐巾
源程序名napkin.?
?
?
（pas,c,cpp）
可执行文件名napkin.exe
输入文件名napkin.in
输出文件名napkin.out
【问题描述】
一个餐厅在相继的N天里，第i天需要Ri块餐巾（i=l，2，…，N）。
餐厅可以从三种途径获得餐巾。
（1）购买新的餐巾，每块需p分；
（2）把用过的餐巾送到快洗部，洗一块需m天，费用需f分（f如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
（3）把餐巾送到慢洗部，洗一块需n天（n>m），费用需s分（s在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。
在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。
【输入】
输入文件共3行，第1行为总天数；第2行为每天所需的餐巾块数；第3行为每块餐巾的新购费用p，快洗所需天数m，快洗所需费用f，慢洗所需天数n，慢洗所需费用s。
【输出】
输出文件共n+1行。
第1行为最小的费用。
下面的n行为从第1天开始每天需要的总餐巾数、需购买的新餐巾数、结束时往快、慢洗部送洗的餐巾数以及用到的来自快洗的餐巾数和来自慢洗的餐巾数。
【样例】
napkin.innapkin.out
364
324331200
101623212010
400022
【算法分析】
在思考这个问题时，一般容易想到从洗的角度去思考，这就必然要对每天的餐巾来源进行分类穷举，当天数较长，每天需求量较大时，穷举的数量级至少为每天的餐巾数之积，程序很难在规定时间内运行出最优解。
如果从买的角度去思考这个问题，则该问题就变得十分简单。
在确定要买的餐巾数之后，显然这些餐巾购买得越早，被反复利用的可能就越大。
也就是说，这些餐巾必须在最早的几天中购买，余下的缺口用洗出来的餐巾来填补，对每天用下来的餐巾，假设全部都送洗，但送洗时不确定其状态，即它们有可能被快洗，有可能被慢洗，也可能不用洗，其状态在今后被选用时再确定。
在确定每天的需求时，除去买的，剩下的首先要选用慢洗为好。
这种餐巾有多少应用多少，不够再选用快洗出来的餐巾。
选用快洗出来的餐巾时，应选用最近的若干天中才快洗出来的餐巾，这样可以保证有更多的餐巾被慢洗出来。
这就是我
们的贪心思想。
对所要购买的餐巾数进行穷举，开始时其值为所需用餐巾数之和，当购买量太少而周转不过来时，程序结束。
在确定了购买的餐巾总数后，按上述算法构造出最
升级会员 