高中信息竞赛贪心算法

贪心策略高中信息竞赛贪心算法共55页，您现在浏览的是第1页!引例【问题描述】：在N行M列的正整数矩阵中,要求从每行中选出1个数,使得选出的总共N个数的和最大。

【试题分析】：本题可用贪心策略：选n次,每一次选相应行中的最大值即可。读入n,m,矩阵数据；total=0;for(i=1;i<=n;i++)//对n行进行选择{选择第i行最大的数,记为k；total+=k；}输出最大总和total；高中信息竞赛贪心算法共55页，您现在浏览的是第2页!贪心算法贪心的定义：指从问题的初始状态出发，向给定的目标推进。但不同的是，推进的每一步不是依据某一固定的递推式，而是作一个当时看似最佳的贪心策略，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。重点：贪心策略的选取。贪心与递推的区别是：推进的每一步不是依据一个固定的递推式,而是做一个当时看似最优的贪心选择。鼠目寸光高中信息竞赛贪心算法共55页，您现在浏览的是第3页!引例2：在一个N×M的方格阵中,每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径,使其从左下角至右上角所经过的权之和最大。【分析】本题用贪心策略不能得到最优解,我们以2×4的矩阵为例。若按贪心策略求解,所得路径为：1,3,4,6；若按动态规划法求解,所得路径为：1,2,10,6。贪心是一种解题策略,也是一种解题思想使用贪心方法需要注意局部最优与全局最优的关系,选择当前状态的局部最优并不一定能推导出问题的全局最优高中信息竞赛贪心算法共55页，您现在浏览的是第4页!应用举例1---部分背包问题【问题描述】：给定一个最大载重量为M的卡车和N种食品,有食盐,白糖,大米等。已知第i种食品最多拥有Wi公斤,其商品价值为Vi元/公斤,编程确定一个装货方案,使得装入卡车中的所有物品总价值最大。【试题分析】：因为每一个物品都可以分割成单位块,单位块的利益越大显然总收益越大,所以它局部最优满足全局最优,可以用贪心法解答,方法如下：先将单位块收益按从大到小进行排列,然后用循环从单位块收益最大的取起,直到不能取为止便得到了最优解。高中信息竞赛贪心算法共55页，您现在浏览的是第5页!贪心策略求解的问题因此,利用贪心策略解题,需要解决两个问题：首先,确定问题是否能用贪心策略求解；一般来说,适用于贪心策略求解的问题具有以下特点：1.可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题,一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后,原问题将变成一个相似的,但规模更小的问题,而后的每一步都是当前看似最佳的选择,且每一个选择都仅做一次。2.原问题的最优解包含子问题的最优解,即问题具有最优子结构的性质。在背包问题中,次选择单位质量最大的货物,它是个子问题的最优解,第二次选择剩下的货物中单位重量价值最大的货物,同样是第二个子问题的最优解,依次类推。其次,如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解,在确定采用贪心策略解决问题时,不能随意的判断贪心标准是否正确,尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。高中信息竞赛贪心算法共55页，您现在浏览的是第6页!贪心策略：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则输出最后一个数字；否则删除个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。重复上述过程s次为止，剩下的数字便是问题的解。N=178546=17546=1546=146=14高中信息竞赛贪心算法共55页，您现在浏览的是第7页!应用举例3---纪念品分组2005

Description：元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。Input：输入文件group.in包含n+2行:

第1行包括一个整数w，为每组纪念品价格之和的上限，第2行为一个整数n，表示购来的纪念品的总件数G

第3-n+2行每行包含一个正整数Pi(5<=Pi<=w)w表示所对应纪念品的价格。Output：输出文件group.out仅一行，包含一个整数，为最少的分组数目和。高中信息竞赛贪心算法共55页，您现在浏览的是第8页!方法一：用快排【思想】贪心，排序，2个指针扫描最小和最大配，可以的i+1,j-1，不行j-1，直到i>j；

voidsolve(){inti=1,j=n,pair=0;while(i<j){if(a[i]+a[j]<=w){i++;j--;}elsej--;pair++;}if(i==j)pair++;cout<<pair<<endl;}高中信息竞赛贪心算法共55页，您现在浏览的是第9页!应用举例4---排队打水问题【问题描述】：有N个人排队到R个水龙头去打水,他们装满水桶的时间为T1,T2,…,Tn为整数且各不相等,应如何安排他们的打水顺序才能使他们花费的时间最少？【分析】：由于排队时,越靠前面的计算的次数越多,显然越小的排在越前面得出的结果越小(可以用数学方法简单证明),所以这道题可以用贪心法解答,基本步骤：1.将输入的时间按从小到大排序；2.将排序后的时间按顺序依次放入每个水龙头的队列中；3.统计，输出答案。高中信息竞赛贪心算法共55页，您现在浏览的是第10页!方法与技巧

运用贪心策略解题时，有的题目有不止一种可能的贪心标准，但不一定每种贪心标准都能够得到正确的结果。因此，在运用贪心法时，一定要仔细分析，选择恰当的贪心标准。高中信息竞赛贪心算法共55页，您现在浏览的是第11页!应用举例7---数列极差问题1647

Description：在黑板上写了N个正整数组成的一个数列，进行如下操作：每次擦去其中的两个数a和b，然后在数列中加入一个数a×b＋1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min，则该数列的极差定义为M＝max－min。

请你编程，对于给定的数列，计算极差。Input：个数N表示正整数序列长度（0＜＝N＜＝50000），随后是N个正整数。N为0表示输入结束。Output：计算极差SampleInput31230SampleOutput：2

高中信息竞赛贪心算法共55页，您现在浏览的是第12页!应用举例8---均分纸牌【试题分析】我们要使移动次数最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。因此，我们将相邻两堆间的移动次数限定在一次或零次。高中信息竞赛贪心算法共55页，您现在浏览的是第13页!贪心的经典应用高中信息竞赛贪心算法共55页，您现在浏览的是第14页!【培训试题】活动选择1649

Description学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。

现在给出n个活动使用礼堂的起始时间Bi和结束时间Ei(Bi<Ei)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。Input行一个整数n(n<=1000)；

接下来的n行，每行两个整数，个Bi，第二个是Ei(Bi<Ei<=32767)Output：输出最多能安排的活动个数。高中信息竞赛贪心算法共55页，您现在浏览的是第15页!二、区间选点•给n个闭区间[ai,bi],在数轴上选尽量少的点,使每个区间内至少有一个点。分析：如果可以按照所有区间的结束位置排序,结束位置相同的项,开始位置小的项在前面。从区间1到区间n进行循环,对于当前区间,若集合中的数不能覆盖它,则从区间末尾向前扫描,若当前数没在集合中出现,则将该数加入集合,直至使集合能覆盖该区间为止。高中信息竞赛贪心算法共55页，您现在浏览的是第16页!高中信息竞赛贪心算法共55页，您现在浏览的是第17页!【培训试题】线段覆盖1893

Description:给出数轴上N条线段,第i条线段用两个数表示Ai,Bi(Ai<Bi),表示从Ai到Bi的一条线段。现在请求出它们覆盖数轴上的多长距离(Ai、Bi的绝对值可能达到10^9)。Input:行：N,以后N行，每行两个数：AiBiOutput:一个数，表示覆盖长度SampleInput328-11510SampleOutput：10

高中信息竞赛贪心算法共55页，您现在浏览的是第18页!高中信息竞赛贪心算法共55页，您现在浏览的是第19页!例：加工生产调度【问题描述】：某工厂收到了n个产品的订单,这n个产品分别在A、B两个车间加工,并且必须先在A车间加工后才可以到B车间加工。某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序,才能使总的加工时间最短。这里所说的加工时间是指：从开始加工个产品到最后所有的产品都已在A、B两车间加工完毕的时间。【输入】：行仅—个数据n(0<n<1000),表示产品的数量。接下来n个数据是表示这n个产品在A车间加工各自所要的时间(都是整数)。最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数)。【输出】：行一个数据,表示最少的加工时间；第二行是一种最小加工时间的加工顺序。【样例输入】：535871062149【样例输出】：34高中信息竞赛贪心算法共55页，您现在浏览的是第20页!例如：N=5（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排在后面；加入m3之后的加工顺序为(，，，，3)；处理m2：∵m2=b2∴m2排在后面；加入m2之后的加工顺序为(，，，2，3)；处理m1：∵m3=a1∴m1排在前面；加入m1之后的加工顺序为(1，，，2，3)；处理m4：∵m4=b4∴m4排在后面；加入m4之后的加工顺序为(1，，4，2，3)；处理m5：∵m5=b5∴m5排在后面；加入m5之后的加工顺序为(1，5，4，2，3)；则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。问题是这种贪心策略是否正确呢？还需证明。高中信息竞赛贪心算法共55页，您现在浏览的是第21页!五、任务时间表问题•有n个任务,每个任务都需要1个时间单位执行.任务i的截止时di(1<=di<=n)表示要求任务i在时间di前结束.误时惩罚wi表示若任务i未在时间di之前结束将导致wi的惩罚;•确定所有任务的执行顺序,使得最惩罚最小;高中信息竞赛贪心算法共55页，您现在浏览的是第22页!•贪心算法：先把罚款E中元素按照权值从大到小排序为e1,e2,…按照e1,e2,…的顺序，尝试添加到当前集合S里；–如果添加之后S仍是独立集，则添加成功–如果S不是独立集，则由定义知以后无论怎样继续添加元素，得到的集合都不可能重新成为独立集，因此不能进行此添加操作；高中信息竞赛贪心算法共55页，您现在浏览的是第23页!SampleInput6610470340260450130420SampleOutput:50高中信息竞赛贪心算法共55页，您现在浏览的是第24页!例如:任务i1234567期限di4243146罚款wi70605040302010最初,我们设所有n个时间空位都是空的。然后按罚款的单调递减顺序(任务1,任务2,任务3,任务4,任务5,任务6,任务7)对各个子任务作贪心选择。在考虑任务j时,如果有一个恰处于或前于dj的时间空位仍空着,则将任务j赋与最近的这样的空位,并填入;如果不存在这样的空位,则将任务j赋与一个还未被占的、最近的空位。按上述贪心策略选择了任务1,2,3,4,7,放弃任务5,6。最终的最优调度为〈2,4,3,1,7,5,6〉,其总的罚款为W5+W6＝50。高中信息竞赛贪心算法共55页，您现在浏览的是第25页!高中信息竞赛贪心算法共55页，您现在浏览的是第26页!Description：在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。【培训试题】合并果子1059高中信息竞赛贪心算法共55页，您现在浏览的是第27页!longlonga[10001],b[10001],c[20001]={0},m,n,i,p,x=1,y=1,minn,sum=0,blen=0;intmain(){cin>>n;for(i=1;i<=n;i++){cin>>m;c[m]++;b[i]=2000000000;}m=0;for(i=1;i<=20000;i++)while(c[i]){a[++m]=i;c[i]--;}for(i=1;i<=n-1;i++){minn=2000000000;

if(a[x]+a[x+1]<minn&&x<=n-1){minn=a[x]+a[x+1];p=1;}if(a[x]+b[y]<minn&&(x<=n&&y<=blen)){minn=a[x]+b[y];p=2;}if(b[y]+b[y+1]<minn&&y<=blen-1){minn=b[y]+b[y+1];p=3;}sum+=minn;b[++blen]=minn;if(p==1)x=x+2;if(p==2){x++;y++;}if(p==3)y=y+2;}cout<<sum<<endl;核心代码高中信息竞赛贪心算法共55页，您现在浏览的是第28页!例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。高中信息竞赛贪心算法共55页，您现在浏览的是第29页!几个简单的贪心问题

【最优装载问题】：给n个物体,第i个物体重量为wi,选择尽量多的物体,使得总重量不超过C;【部分背包问题】:有n个物体,第i个物体的重量为wi,价值为vi,在总重量不超过C的情况下让总价值尽量高;【乘船问题】:有n个人,第i个人重量为wi.每艘船的载重量为C,最多乘两个人.用最少的船装载所有人;贪心策略:最优装载问题:先拿轻的贪心策略:部分背包问题:先拿性价比高的贪心策略:乘船问题:最轻的人和尽量重的人配对;高中信息竞赛贪心算法共55页，您现在浏览的是第30页!问题初始化；//读入数据按vi从大到小将商品排序；i=1;While(m>=0&&i<=n){if(m=0)return;//如果卡车满载则跳出循环m=m-wi;if(m>=0)将第i种商品全部装入卡车；else将m+wi重量的物品i装入卡车;i=i+1;//选择下一种商品}程序框架结构高中信息竞赛贪心算法共55页，您现在浏览的是第31页!应用举例2---删数问题【问题描述】：键盘输入一个高精度的正整数n（n<=240位）,去掉其中任意s个数字后剩下的数字按照原来的次序将组成一个新的正整数。编程对给定的n和s,寻求一种方案,使得剩下组成的新数最小。输入：1785464输出：14高中信息竞赛贪心算法共55页，您现在浏览的是第32页!cin>>s>>m;n=s.length();for(i=0;i<m;i++){for(j=0;j<n-1;j++)if(s[j]>s[j+1])//删除个递减区间的首字符 { for(k=j;k<n-1;k++)s[k]=s[k+1]; break; }n--;//否则删除递增区间的最后一个元素}i=0;while(s[i]==‘0’)i++;//去掉前面的0for(j=i;j<n;j++)cout<<s[j];高中信息竞赛贪心算法共55页，您现在浏览的是第33页!应用举例3---纪念品分组2005

SampleInput1009902020305060708090SampleOutput：6

高中信息竞赛贪心算法共55页，您现在浏览的是第34页!方法二：用桶排序intmax,n,p,a[201]={0},t=0,i,j;cin>>max>>n;for(i=1;i<=n;i++){cin>>p;a[p]++;}//桶排序for(i=max;i>=1;i--)//分组while(a[i]){a[i]--;t++;for(j=max-i;j>0;j--)if(a[j]){a[j]--;break;}}cout<<t<<endl;高中信息竞赛贪心算法共55页，您现在浏览的是第35页!应用举例5---取数游戏2341

Description：给出2n(n<=100)个自然数(小于等于30000)。将这n个自然数排成一列，游戏双方A和B从中取数，只允许从两端取数。A先取，然后双方轮流取数。取完时，谁取得数字总和最大为取胜方；若双方和相等，属B胜。试问A方是否有必胜策略？Input：两行，行一个整数n；第二行有2*n个自然数。Output：行：若A有必胜策略，则输出'yes'，否则输出'no'SampleInput479364253SampleOutput：yes高中信息竞赛贪心算法共55页，您现在浏览的是第36页!应用举例6---混合牛奶1648

Description牛奶包装是一个如此低利润的生意,所以尽可能低的控制初级产品(牛奶)的价格变的十分重要。请帮助快乐的牛奶制造者(merrymilkmakers)以可能的最廉价的方式取得他们所需的牛奶。快乐的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同。而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,快乐的牛奶制造者从每个农民那购买一定量的牛奶,少于或等于农民所能提供的最大值。

给出快乐牛奶制造者的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算快乐的牛奶制造者所要付出钱的最小值。注意:每天农民生产的牛奶的总数对快乐的牛奶制造者来说足够的。Input第1行:二个整数,n和m。

个数值,n,(0<=n<=2,000,000)是快乐的牛奶制造者的一天需要牛奶的数量。

第二个数值,m,(0<=m<=5,000)是他们可能从农民那买到的数目。

第2到m+1行:每行二个整数,pi和ai。

pi(0<=pi<=1,000)是农民i牛奶的价格。

ai(0<=ai<=2,000,000)是农民i一天能卖给快乐的牛奶制造者的牛奶数量。Output：单独的一行包含单独的一个整数，表示快乐的牛奶制造者拿到所需的牛奶所要的最小费用

高中信息竞赛贪心算法共55页，您现在浏览的是第37页!应用举例7---均分纸牌[问题描述]有N堆纸牌，编号分别为1，2，…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如N=4，4堆纸牌数分别为：

①9②8③17④6

移动3次可达到目的：

从③取4张牌放到④（981310）->从③取3张牌放到②（9111010）->从②取1张牌放到①（10101010）。[输入]：N（N堆纸牌，1<=N<=100）

A1A2…An（N堆纸牌，每堆纸牌初始数，l<=Ai<=10000）[输出]：所有堆均达到相等时的最少移动次数。‘[输入输出样例]

4

98176

屏慕显示：3高中信息竞赛贪心算法共55页，您现在浏览的是第38页!应用举例7---均分纸牌【分析】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边（第2堆）-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。高中信息竞赛贪心算法共55页，您现在浏览的是第39页!一、不相交的区间选择•给n个开区间[Si,Fi],选择尽量多的区间,使得两两不交。•算法:首先按照结束时间f1<=f2<…<=fn的顺序排序,依次考虑各个活动,如果没有和已经选择的活动冲突,就选;否则就不选。•正确性:如果不选f1,假设个选择的是fi,则如果fi和f1不交叉则多选一个f1更划算;如果交叉则把fi换成f1不影响后续选择。高中信息竞赛贪心算法共55页，您现在浏览的是第40页!SampleInput113514121481206811610573859213SampleOutput：4高中信息竞赛贪心算法共55页，您现在浏览的是第41页!【培训试题】整数区间1650

Description：一个整数区间[A,B],A

请编程完成以下任务：

1.从文件中读取区间的个数及其它们的描述；

2.找到满足下述条件的所含元素个数最少的集合中元素的个数,对于每一个区间,都至少有两个不同的整数属于该集合。Input：首行包括区间的数目n,1<=n<=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。Output：行集合元素的个数,对于每一个区间都至少有两个不同的整数属于该区间,且集合所包含元素数目最少。SampleInput：436240247SampleOutput:4高中信息竞赛贪心算法共55页，您现在浏览的是第42页!三、区间覆盖•给n个闭区间[ai,bi],选择尽量少的区间覆盖一个给定线段[s,f]。•算法:对于每个区间,删除在[s,f]之外的部分,并按a1<=a2<…<=an的顺序排序,a相同时按b从大到小排序.从左到右扫描,如果当前区间可以覆盖新的部分,选择此线段。高中信息竞赛贪心算法共55页，您现在浏览的是第43页!高中信息竞赛贪心算法共55页，您现在浏览的是第44页!四、流水作业调度•n个作业要在由两台机器M1和M2组成的流水线上完成加工.每个作业i必须先在M1上然后在M2上加工,时间分别为ai和bi；•确定这n个作业的加工顺序,使得从个任务开始在M1上加工到最后一个任务在M2上加工完成的总时间尽量小；•直观上,最优调度一定让M1没有空闲,M2的空闲时间尽量少；•Johnson算法.设N1为a<b的作业集合,N2为a>=b的作业集合,将N1的作业按a非减序排序,N2中的作业按照b非增序排序,则N1作业接N2作业构成最优顺序.•程序易于实现,时间O(nlogn),关键在于正确性证明。高中信息竞赛贪心算法共55页，您现在浏览的是第45页!【算法分析】：本题求一个加工顺序使得加工总时间最短,要使时间最短,则就是让机器的空闲时间最短。一旦A机器开始加工,则A机器将会不停的进行作业，关键是B机器在加工过程中,有可能要等待A机器。很明显个部件在A机器上加工时，B机器必须等待,最后一个部件在B机器上加工,A机器也在等待B机器的完工。可以大胆猜想,要使总的空闲的最少,就要把在A机器上加工时间最短的部件最先加工,这样使得B机器能以最快的速度开始加工;把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：设Mi=min{ai,bi}将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的已经作业后面，若Mi=bi，则将它排在从尾开始的作业前面。高中信息竞赛贪心算法共55页，您现在浏览的是第46页!算法流程如下：forI:=1toNdo {求M数组}ifA[I]<B[I]thenM[I]:=A[I] elseM[I]:=B[I]；将M从小到大排序；S:=1;T:=N; {首位指针初始化}forI:=1toNdoif对于第I小的工序J，若A[J]<B[J]thenbeginOrder[S]:=J;{将工序J插在加工序列的前面}S:=S+1;endelsebeginOrder[T]:=J;{将工序J插在加工序列的后面}T:=T-1;end;高中信息竞赛贪心算法共55页，您现在浏览的是第47页!分析：•称在限期内完成的任务为早任务,收到罚款的任务为迟任务.如果早任务紧跟在迟任务之后,交换之后总罚款不变；•假设对于相邻两个早任务i和i+1.由于两个任务都是早任务,因此tj+1<=dj+1.若di>di+1,则ti+1<=di+1<di,交换以后显然i+1的时间更早,仍然是早任务;i的时间ti’=ti+1<di仍然是早任务,总罚款不变；•规范形式:所有早任务在迟任务前,且按限期非递减排序.•关键:选哪些作为早任务?•不是任选一些任务作为早任务都是可行的.对于一个早任务集合S,如何判断它是否可行呢?只需要对S内的元素按限期非递减排序,然后一一放置；高中信息竞赛贪心