程序设计中的基本算法(修改).ppt

程序设计中的基本算法,什么是算法？ 简单来说算法是解决问题的方法和步骤，它不是问题的答案，但它是经过准确定义的，用来获得答案的过程。 一个好的算法，占用空间小，运行时间短，计算机科学家和程序设计员一直在追求更高效的算法。,模拟法,有些问题的描述和解决方法已经很清楚，只需要按照描述去一步一步的执行即可，这种方法就是计算机解决问题的一种最普遍最直接的方法模拟法。模拟法并不是算法，它只是我们依赖计算机的运算速度解决问题的一种方法或模式，针对具体问题设计具体的程序。 模拟法适用于问题求解清晰，运算规模较小的问题，如果问题求解的时空代价很大就要考虑是否有其它更优的解决方案。,例题1：酗酒的狱警 某监狱里有个很长的走廊,走廊中一个接一个有n个房间。每个房间中锁着一个犯人。一天夜里,狱警决定玩一个无聊游戏。第一轮中,他喝了一口威士忌,然后打开走廊间每个房子。第2轮,他喝了一口威士忌,然后按2的倍数遍历每个房子，第3轮，他又喝了一口威士忌，遍历所有3的倍数的房间，依次类推。在遍历中，如果房间是锁的，则打开否则锁上。他这样重复n轮,最终醉酒。这时有些囚犯人看到自己房间的所以打开，他们立即逃跑。对于有n间房子的走廊，最终会有多少囚犯逃脱。 输入：第一行中输入一个整数表示有多少组测试数据。接下来的若干行，每行包含一个5至100整数,这是房间的数目，输出：对应输入数据输出多行，每行一个整数，表示逃脱的囚犯数量。 样例输入： 2 5 100 样例输出： 2 10,【问题分析】： 由于问题的规模较小，按照题意用一个200个元素的布尔型数组表示房间的状态，“true”表示房间门是关闭的，“false”表示房间门是开的。每次遍历数组，将当前数到数的倍数元素的状态反转，最后遍历数组统计房间开着的个数输出。 【程序实现】： program exp1_1; var num,s,n,m,i,k,j:integer; a:array0200 of boolean; begin readln(num); 读入测试数据的个数 for i:=1 to num do begin readln(n); 读入房间数 fillchar(a,sizeof(a),true); for j:=1 to n do for k:=1 to n do if k mod j=0 then ak:=not ak; s:=0; for j:=1 to n do 统计个数 if aj=false then inc(s); writeln(s); end; end.,例题2：分发糖果 一些学生围绕老师座着，每人手里都有偶数个糖果，现在老师吹一声哨子，所有学生同时将自己的一半糖果给他右边的同学，如果某个同学手里的糖果个数是奇数则老师给他一个糖果。重复这个过程直到所有同学手中的糖果数一致。 写一个程序判断老师要吹多少下哨子每人手中的糖果数才能一致，结束后每人手里又有多少个糖果。 输入： 包含多组数据，每组数据的第一行是一个数字n，表示学生的个数，下面的n行以顺时针次序，每行一个数字表示每个学生手里的糖果个数，输入以学生个数为0结束。 输出： 对于每组数据输出一行包含两个数据，老师吹哨子的次数和学生最后平均的糖果数，中间以空格相隔。,样例输入： 6 36 2 2 2 2 2 11 22 20 18 16 14 12 10 8 6 4 2 4 2 4 6 8 0,样例输出： 15 14 17 22 4 8,【问题分析】： 首先判断每个人的糖果数是否相等，如果相等则分配结束，否则开始重新分配过程。由于题目中说明是同时将每人手里的糖果数的一半给右边的人，而用程序实现时是逐句执行，因此若用ai表示每人手里的糖果数，q表示第i-1位手中的原糖果数，则有： ai:=ai div 2 + q div 2 接下来判断这时ai是否是奇数，如果是奇数，教师再给他一个糖果并计数，重复上面的过程直到每人手里的糖果数相等。,枚举法,枚举法解决问题的基本思路是依次枚举问题的所以可能解，按照问题的约束条件进行判断，如果满足约束条件则得到一组解，这个过程不断的进行下去最终得到整个问题的解。可以说模拟法主要关心问题“怎么做”，枚举法主要关心当前的可能解“是不是”。 要用枚举法解决问题，首先需要知道解的范围并能以合适的方法列举，其次要对问题的约束条件进行精确的描述，这两个环节有一个疏漏就有可能丢失正确解或多出错误解。枚举法虽然实现起来很容易，但对于大数据量的枚举效率是很低的。,例题3：四人中有一人是小偷，现在警察得到了这样的证词： A说：不是我。 B说：是C。 C说：是D。 D说：他胡说。 已知3个人说的是真话，一个人说的是假话。现在要根据这些信息，确认小偷是谁。 【问题分析】： 假设小偷是“thisman”，由于“thisman”的取值无非是A、B、C、D，如果我们让“thisman”的取值依次是AD，分别对4个关系式求值，如果为“True”的表达式有3个那么这时“thisman”的值就是问题的解。 已知的证词可以表示为： “证词表述” 证词 语句表示 A说：不是我 ThismanA; B说：是C Thisman=C; C说：是D Thisman=D; D说：他胡说 ThismanD;,program exp1_3; var n:integer; t:char; begin for t:='A' to 'D' do begin n:=ord(tA)+ord(t=C)+ord(t=D)+ord(tD); if n=3 then writeln('thisman is ',t); end; end.,例题4： 数字三角形（NOIP1997普及组第2题） 把1，2， 9共9个数排成下列形状的三角形： a b c d e f g h i 其中：ai分别表示1，2，.9中的一个数字，并要求同时满足下列条件： (1) afi （2）bd, gh， ce； （3）abdf fghi ieca P 程序要求：根据输入的边长之和P，输出所有满足上述条件的三角形的个数及方案。 【问题分析】： 按题意直接直接枚举就行。注意利用每个数之间的大小关系。在检测是用一个数组保存出现的数字，检测数组第19个元素就可以分辨19这9个数字是否不重复的出现。,program exp2_3; var a,b,c,d,e,f,g,h,i,k,p,sum:integer; bb:array-100100 of byte; begin readln(p); sum:=0; for a:=1 to 7 do for b:=1 to 8 do for c:=1 to 8 do for g:=1 to 8 do for f:=a+1 to 8 do for i:=f+1 to 9 do begin d:=p-a-b-f; if d=b then break; h:=p-f-g-i; if h=g then break; e:=p-a-c-i; if e=c then break; fillchar(bb,sizeof(bb),0); bba:=1;bbb:=1;bbc:=1;bbd:=1;bbe:=1;bbf:=1;bbg:=1;bbh:=1;bbi:=1; for k:=1 to 9 do if bbk=0 then break; if bbk=1 then begin inc(sum); writeln(a:3,b:3,c:3,d:3,e:3,f:3,g:3,h:3,i:3); end; end; writeln(sum); end.,例题5：一根29cm长的尺子，只允许在上面刻7个刻度，要能用它量出129cm的各种长度。试问这根尺子的刻度该怎么选择？ 问题分析： 从129cm中选择7个刻度的所有可能情况是C729 =1560780 对于每一组刻度的选择都需要判断是否能将129cm的各种刻度量出来。例如选择的刻度为：a1,a2,a3,a4,a5,a6,a7那么能量出的刻度为： a1, 29a1 2 a2, a2a1, 29a2 3 a3, a3a1, a3a2, 29a3 4 a4, a4a1, a4a2, a4a3, 29a4 5 a5, a5a1, a5a2, a5a3, a5a4, 29a5 6 a6, a6a1, a6a2, a6a3, a6a4, a6a5, 29a6 7 a7, a7a1, a7a2, a7a3, a7a4, a7a5, a7a6, 29a7 8 可量出2+3+4+5+6+7+8种刻度，即35种刻度。事实上期中有许多刻度是重复的，不可能覆盖129。例如：a1,a2,a3,a4,a5,a6,a7为1，3，6，10，15，21，28时，能量出的可度为： 1，28 3，2，26 6，5，3，23 10，9，7，4，19 15，14，12，9，5，14 21，20，18，15，11，6，8 28，27，25，22，18，13，7，1 缺16，17，24（29即尺子长度）,如果找出了刻度a1,a2,a3,a4,a5,a6,a7那么我们就可以利用对称性29-an 来求另一组解，所以求解过程中可仅考虑a1a2a3a4a5a6a7的情况。 很显然要使1，28两种刻度能量出来，则在7个刻度中就必须有1或28；这样就可以设a1=1（或a1=28）。题解就变成了在227中选取6个刻度的问题了。其刻度数目为C626=230230。 这样解的范围就从百万数量级变成了十万的数量级，大大减少了运行次数。因此，我们在用穷举法求问题解时，应注意程序的优化，尽可能减少搜索时间。 为了判定7个刻度是否能够度量129的所有长度，可以用集合的方法，也可以用数组的0，1数据判断。,program ex5_kedu; const n=29; m=1; var a:array17 of integer; b:array1n of 01; 记录能量的刻度 f:boolean; i,j:integer; begin a1:=m; for a2:=2 to n-7 do for a3:=a2+1 to n-6 do for a4:=a3+1 to n-5 do for a5:=a4+1 to n-4 do for a6:=a5+1 to n-3 do for a7:=a6+1 to n-2 do begin for i:=1 to 29 do bi:=0; for i:=1 to 7 do begin bai:=1;bn-ai:=1;bn:=1; 初始化 for j:=i+1 to 7 do babs(aj-ai):=1 end; j:=0; for i:=1 to n do j:=j+bi; if j=n then begin for i:=1 to 7 do write(ai:4); writeln end; end; end.,例题6：邮局发行一套四种面值的邮票，如果每封信所贴邮票张数不超过3张，存在整数r，使得用不超过三枚的邮票，可以贴出连续的整数1、2、3、r来，找出这四种面值邮票，使得r值最大。 问题分析： 本题与上题有相似之处，上题知道总长，搜索7个刻度，而本题则是知道每封信邮票数的范围（=3），邮票有四种面值，编程找出能使连续面值最大的邮票。 算法如下： 面值不同的四种邮票，每封信所贴邮票数不超过3张； 用这四种邮票贴出连续的整数，并且使得 r 值最大； 用穷举法，找出所有符合条件的解； 利用集合的方法统计邮票的面值，提高判重的速度。程序优化 设四种邮票的面值分别为 a，b，c，d，根据题意设 abcd，因此a=1，用循环语句完成搜索。,program ex6_youpiao; var a,b,c,d:integer; x,x0,x1,x2,x3,x4:integer; st1:set of 1100; function number(a,b,c,d:integer):integer; var n1,n2,n3,n4,sum:integer; begin st1:=; for n1:=0 to 3 do for n2:=0 to 3-n1 do for n3:=0 to 3-n1-n2 do for n4:=0 to 3-n1-n2-n3 do if n1+n2+n3+n4x0 then begin x0:=x; x1:=a; x2:=b; x3:=c; x4:=d; write(x1:5,x2:5,x3:5,x4:5); writeln('':10,'x0=',x0); end; end; end.,贪心法,问题的可行解 问题的最优解 每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行解，使优化函数取得最佳值的可行解称为最优解。 贪心法从问题的某一个初始解出发，采用逐步构造最优解的方法向给定目标推进。在每个局部阶段，都做出一个看上去最优的决策（即某种意义下的、或某个标准下的局部最优解），并期望通过每次所做的局部最优选择产生出一个全局最优解。 做出贪心决策的依据称为贪心准则（策略），决策一旦做出，就不可更改。,最优化问题,例题7：删数问题 键盘输入一个高精度的正整数n（240位），去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻求一方案，使得剩下的数字组成的新数最小。 输入： n s 输出：最后剩下的最小数 样例输入：178543 4 样例输出：13 问题分析： 正整数的位数为240位 如何决定哪s位被删除？是否是最大的连续s位的数字？ 贪心策略：每一步总是选择一个使得剩下的数最小的数字删去 实现方法：按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。这样便形成一个新的字符串，然后回到串首，按上述的规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解。,n =178543 删掉8 17543 删掉7 1543 删掉5 143 删掉4 13,字符串类型存贮n,program ex6_shanshu; var i,j,k,s:integer; n:string; begin readln(n); readln(s); while s0 do begin i:=1; while (i1)and(n1='0') do delete(n,1,1); writeln(n); end.,删数问题与如何寻找递减区间首字符的问题对应起来。 注意：字符串串首有若干个0的情况，甚至字符串都是0的情况。,例题8：最大数问题 设有n个正整数（n20），将它们连成一排，组成一个最大的多位整数。例如：n=3时，3个整数13、312、343连成的最大整数为34331213。 输入：包括两行，第一行是一个整数n，第二行有n个整数，它们之间以空格隔开。 输出：连成的多位数。 样例输入：3 13 312 343 样例输出：34331213 问题分析： 利用贪心法则，在待选数中由高位向低位选择较大的数。对待选的数按字典顺序排序，以排序结果依次取数。 若待选数为24、241，则连成的最大数为24241。 改变原先比大小的方法，用A和B表示两个待选数，如果AB比BA大则说A比B“大”，不断地在待选数中贪“大”，就可得到最大数。,program ex8_zuidashu; var n,x,i,j:integer; s:array040 of string; begin readln(n); for i:=1 to n do begin read(x); str(x,si); end; for i:=1 to n-1 do for j:=1 to n-1 do if sj+sj+1sj+1+sj then begin s0:=sj; sj:=sj+1; sj+1:=s0; end; for i:=1 to n do write(si); writeln; end.,例题9：比赛预言 假设有M个人，包括你在内玩一种纸牌游戏。开始时，每一个游戏者接到N张牌，牌的分值是一个正整数，最大是M×N，并且牌的分值各不相同。在一轮中，每个游戏者选一张牌和其他人比较。如果你的牌最大则你就赢了这轮，接着开始下一轮。N轮后，所有的牌都比较完毕，赢的轮次最多的人赢得比赛。 游戏开始时给你发牌，写一个程序判断你至少可以赢多少轮。 输入：由多组测试数据构成。每组测试数据的第一行包含两个整数m（2m20）和n（1n50），表示游戏参与者和每个人接到的牌的数量。下面的一行是你接到的牌的分值，每组数据后有一个空行隔开不同的测试数据。输入数据以一行中的两个0表示输入结束。 输出：对应每组测试数据，输出至少赢得的轮次，一行内包括测试数据的序号，格式如样例所示。 样例输入：2 5 1 7 2 10 9 6 11 62 63 54 66 65 61 57 56 50 53 48 00 样例输出：Case 1:2 Case 2:4,问题分析： 开辟一个足够大的一维数组，下标表示所有可能的纸牌的分值，用“*”标记该分值的纸牌是你的，则样例第一组数据如下： 一维数组记录的分数 由于题目是问至少能赢多少轮，也就是说在你现有分值的情况下让你尽可能的多赢。要达到这个效果只要从右侧开始选未标记的结点即可。 具体来说用数组A记录你的分值，同时在布尔型数组F中标记该分值为TRUE（默认为FALSE）。用一个变量win记录至少能赢的次数，初值为0。在F数组中从右至左遍历元素，如果为TRUE增加win，否则减小win,并记录win的最大值即为题解。,1 2 3 4 5 6 7 8 9 10,program ex9_bisai; var k,max,win,top,num,m,min,n,i,j,r,t:longint; a:array05000 of integer; f:array05000 of boolean; begin num:=0; readln(m,n); while (m0)and(n0) do begin inc(num); fillchar(f,sizeof(f),false); for i:=1 to n do begin read(ai); fai:=true; end; readln; max:=0; win:=0; for k:=m*n downto 1 do begin if fk then begin inc(win); if winmax then max:=win; end else dec(win); end; writeln('Case ',num,': ',max); readln(m,n); end; end.,例题10：取数游戏 给出2n（n100）个自然数（数小于等于30000）。游戏双方分别为A方（计算机方）和B方（对弈人）。只允许从数列两头取数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和最大为胜方；若双方和相等，属于A胜。试问A方可否有必胜的策略？ 输入：键盘输入n及2*n个自然数 输出：共3n+2行，其中前3*n行为游戏经过。每行分别为A方所取的数，及B方取数前应给予的适当提示，让游戏者选取哪一头的数（L/R 左端或右端），和B方所取的数。最后2行分别为A方取得的数之和，B方取得的数之和。 问题分析： 设n=4，自然数列为：7 9 3 6 4 2 5 3 。 设计一个贪心策略，让A每次取数列两头最大的 数。 A取：7、3、4、5 B取：9、6、2、3 有效策略：若能够让A方取走“数和较大的奇（偶）位置上的所有数”，则A方胜。,设j为A取数的奇偶位置标志，则j=0表示偶数位置数和较大，A取偶数位置上的所有数；j=1表示奇位置数和交大，A取奇位置的所有数。 设SA，SB分别表示A方取数和，B方取数和（SASB）；a存储2*n个自然数序列；lp，rp为序列左端位置和右端位置；ch为B方取数位置信息（L或R）。 读入n及a； SA:=0;SB:=0; 计算A方取数和、B方取数和，A方取数的位置标志 for i:=1 to n do begin SA:=SA+a2*i-1; SB:=SB+a2*i; end; if SA=SB then j:=1 else begin j:=0; 交换SA和SB； end; lp:=1;rp:=2*n; for i:=1 to n do A方和B方依次进行n次对弈 begin if(j=1)and(lp mod 2=1)or(j=0)and(lp mod 2=0)若A方应取奇位置数且左端位置为奇，或者A方应取偶位置数且左端位置为偶，则A方取走左端位置的数 then begin writeln(alp); lp:=lp+1; end; else begin writeln(arp); rp:=rp-1； end; write('B=L/R'); 提示信息 repeat B方取数，输入L或R readln(ch); if ch='L' then begin write(alp); lp:=lp+1; end; if ch='R' then begin writeln(arp); rp:=rp-1; end; until (ch='L')or(ch='R'); end; 输出A方取数的和SA和B方取数的和SB;,例题：混合牛奶（mixing milk） 包装牛奶是一个如此低利润的生意，所以尽可能低的控制初级产品（牛奶）的价格变得十分重要。请你来帮助包装牛奶制造商，以可能的最廉价的方式取得他们所需要的牛奶。 包装牛奶制造公司从一些农民那里购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同，而且，一只母牛一天只能生产一定量的牛奶，因此农民每一天只能有一定量的牛奶可以卖。 每天，包装牛奶制造商从每个农民那里购买一定量的牛奶（少于或等于农民所能提供的最大值）。 给出包装牛奶制造商每日的牛奶需求，连同每个农民提供的牛奶量和每加仑的价格，请计算应当如何从农民那里购买一定量的牛奶，才能使包装牛奶制造商所要付出的钱最少。 注意：每天农民生产的牛奶的总数对包装牛奶制造商来说是足够的。 输入：第一行 两个整数，N和M 第一个数值N（0N2000000）是包装牛奶制造商一天需要牛奶的数量。 第二个数值M（0 M 5000）是能够提供牛奶的农民的人数。 第2到M+1行 每行两个整数，Pi和Ai,Pi（0 Pi 1000）是农民i牛奶的价格。 Ai（0 Ai 2000000）是农民i一天能卖给包装牛奶制造商的牛奶数量。 输出：一个整数，表示包装牛奶制造商拿到所需的牛奶所要付出的最小费用。 输入样例： 100 5 5 20 9 40 3 10 8 80 6 30 输出样例： 630,贪心策略：不断向当前价格最低的农民购买牛奶，直到买到足够的牛奶为止。 具体算法实现：将所有的价格按照从小到大的排序，然后顺序购买，即每次向当前价格最低的那个农民购买牛奶，如果该农民手上的牛奶数量不足以满足需求，则继续向下一个农民购买，以此类推，直到买到足够多的牛奶，此时得到的即为最优解。,program mixingmilk; var a:array15100 of integer; b:array15100 of longint; c:array15100 of real; n:longint; m:integer; i,j,l:integer; k,t:longint; begin assign(input,'milk.in'); rest(input); assign(output,'milk.out'); rewrite(out); readln(n,m); for i:=1 to m do readln(ai,bi); for i:=1 to m-1 do for j:=i+1 to m do if aiaj then begin t:=ai; ai:=aj; aj:=t; t:=bi; bi:=bj; bj:=t; end;,i:=0; j:=0; k:=0; repeat i:=i+1; if n=bi then begin k:=k+ai*bi; n:=n-bi; end else begin k:=k+ai*n; n:=0; end; until n=0; writeln(k); close(input); close(output); end.,例题：部分背包问题 给定一个最大载重量为M的背包和N种货物。已知第i种货物的重量为Wi，其总价值为Pi，设定M，Wi，Pi均为整数，编程确定一个装货方案， 使得装入背包中的货物总价值最大。 分析：在求解装货方案时，设背包中装入了第i种货物的重量为Xi（0=Xi=Wi）,显然当Xi=0表示背包中没有装入该种货物，问题就转化成如 下形式：确定一组X1,X2,.,XN，使得它们在满足Xi=W（i=1,2,.,N）的条件下，Xi*（Pi/Wi）具有最大值。 这里，设Ti为第i种货物的单位重量的价值，问题的目标函数是总价值S=Xi*Ti，显然，在装入相同重量的货物时，单位重量价值越大，则背 包所装的货物总价值越大。因此容易证明，在装货过程中，为保证背包中所装货物的总价值最大，应尽可能选择单位重量价值越大的物品优 先装入。这样问题的解决就变得非常简单。 算法的简单描述： program bag; begin 读入数据； 计算货物的单位重量价值Ti，并将它们按从大到小排序； 依次选择单位重量较大的货物放入背包，直至不能放入； 输出最大价值总和S和装货方案； end.,例题：合并果子（noip 04-2） 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 【输入文件】 输入文件fruit.in包括两行，第一行是一个整数n(1n=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1ai=20000)是第i种果子的数目。 【输出文件】 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。 【样例输入】 3 1 2 9 【样例输出】 15 【数据规模】 对于30的数据，保证有n=1000： 对于50的数据，保证有n=5000； 对于全部的数据，保证有n=10000。,例题11：活动选择 假设有一个需要使用某一资源的n个活动组成的集合s，s=1，n。该资源一次只能被一个活动所占用，每一个活动有一个开始时间bi和结束时间ei（biei）。若biej或者bjei，则活动i和活动j兼容。 你的任务是：选择有相互兼容的活动组成的做大集合。 输入：输入文件名为act.in，共n+1行，其中第一行为n，第二行到第n+1行表示n个活动的开始时间和结束时间（中间用空格隔开），格式为： n b1 e1 bn en 输出：输出文件名为act.out，共两行，第一行为满足要求的活动占用的时间t，第二行为最大集合中的活动序号，每个数据之间用一个空格隔开。,样例输入：11 3 5 1 4 12 14 8 12 0 6 8 11 6 10 5 7 3 8 5 9 2 13 样例输出：14 2 3 6 8,使用贪心策略如下，每一步总是选择这样一个活动来占据资源：它能够是得余下未调度的时间最大化，使得兼容的活动尽可能多。为达到这个目的，我们将n个待选活动按的结束之间递增的顺序排列： e1 e2 en 首先将递增序列中的活动1进入集合s。然后依次分析递增序列中的活动2至活动n，每次将与s中的活动兼容的活动加入到集合s中。 结合问题的样例输入，先将11个活动的活动号、开始时间、结束时间及递增编号列表如下：,任务序号,占用时间,program exp3_4; type node=record no:integer; b,e:integer; next:integer; end; var a:array01000 of node; t:node; i,j,k,s,l,m,n:integer; begin fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do begin readln(ai.b,ai.e); ai.no:=i; 任务编号 end; for i:=1 to n-1 do 按任务的结束时间排序 begin k:=i; for j:=i to n do if aj.eak.e then k:=j;,if ki then begin t:=ak;ak:=ai;ai:=t; end; end; i:=0; while k0 do begin i:=ai.next; write(ai.no,' ');end; end.,例题:旅行家的预算-lxj（NOIP1999 高中组第三题） 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，N）。 计算结果四舍五入至小数点后两位。 如果无法到达目的地，则输出“No Solution”。 样例： Input D1=275.6 C=11.9 D2=27.4 P=2.8 N=2 油站号I 离出发点的距离Di 每升汽油价格Pi 1 102.0 2.9 2 220.0 2.2 Output 26.95（该数据表示最小费用）,问题分析：设出发城市为0站，目的城市为n+1站。汽车目前在i站（0in），应加多少油，驶往哪一站可以是得整个行程的花费最少？我们不妨采用下面的贪心策略： 下一个目的站的单位油价尽可能低于i站，如果所有可能到达油站的单位油价都高于i站的话，则下一个目的站的单位油价亦应该尽可能的便宜。为此，我们在由i站直接可达的所有油站j（Dj-Di C*D2，i+1 j n+1）中，计算两个油站序号： Min1单位油价低于i站且距离最近（以最小代价到达）的一个油站。 Min2在由i站直接可达的所有油站中，单位油价最便宜（但高于i站）的一个油站。 显然，若min1站存在的话，应成为首选的方向，邮箱仅加入驶往min1站所需的油量（Dmin1-Di）/D2，以便到达min1站时换上更便宜的汽油；反之，若i站直接可达的所有有站的油价均高于i站，则应选择其中油价最低的min2站作为方向，由于i站的油价比min2站的便宜，因此不妨让汽车在i站加满油，或者在直接可达目的城市的情况下（D1-Di）/D2 C加入驶往最终目的地所需的油量。 问题是，汽车在i站时，邮箱有可能尚有剩油，设剩余油量rest。因此只要在i站加入C-rest的油量，便可将油箱加满；如果i站直接可达目的城市，则加入（D1-Di）/D2-rest的油量，便可使汽车最终到达目的城市。,汽车到达min1站时，油箱中的油正好耗尽（rest=0）；否则汽车到达min2站时，油箱内的剩余油量应为rest=rest+need-（Dmin2-Di）/D2 。 我们从0站出发，按照上述方法一次类推，直至到达目的城市n+1为止。设k表示当前站（0 k n+1）；j表示由k站驶往的下一目的站（k j n+1）;need表示汽车在k站加入的油量；cost表示最少费用。 算法框架： K:=0; rest:=0; cost:=0; Repeat j:=k; min1:=0; min2:=0; while (jn+1)and(DjDk C*D2 )do 在k站直接可达的所有油站中，计算油价低于k站且距离 最近的一个油站序号min1和油价最低的一个油站序号min2 begin j:=j+1; if (min1=0)and(pjpk) then min1:=j; if (min2=0)or(pjpmin2) then min2:=j; end;,if j=k 即便在k站装满油，也无法到达任意站点，则失败退出 then begin 输出无解信息； halt; end; if min10 若由k站出发直接可达一个油价更低的油站 then begin need:=(Dmin1-Dk)/D2; 计算k站加入的油量 if need0 then need:=0; 若min1站位于k站左方， 则不需加油 cost:=cost+pk*need; rest:=0; 汽车抵达min1站时油正好耗尽 k:=min1; 由min1出发，继续延伸旅行路线 end else begin 否则，所有可达油站的油价都高于i站 若无法直接到达目的城市，则计算油箱在k站满载时需要加入的油量；否则计算汽车直达目的城市需新增的油量 if C*D2Dn+1 Dk then need:=C*D2-rest else need:=(Dn+1 - Dk)/D2rest; cost:=cost+need*pk; rest:=rest+need-(Dmin2-Dk)/D2; 计算汽车到达min2站时的剩油量 k:=min2; 由min2站出发，继续延伸旅行路线 end; until k=n+1; 直至汽车驶至目的城市为止 输出总费用cost；,例题：线段覆盖 问题描述：给定x轴上的N（0N100）条线段。每个线段由它的两个端点ai和bi确定，i=1，2，