发布时间 : 星期三 文章贪心算法详解(C++版)更新完毕开始阅读
【例3-1】删数问题
【问题描述】
键盘输入一个高精度的正整数n（n<=240位），去掉其中任意s个数字后剩下的数字按原左右顺序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的数最小。 输入： N S 输出：
最后剩下的最小数。 【样例输入】 178543 4
【样例输出】 13
【题解】
由于正整数n的有效位数为240位，所以很自然地采用字符串类型存储n。那么如何解决哪s位被删呢？是不是最大的s个数字呢？为了尽可能的逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下数最小的数字删去。即按高位到低位的顺序搜索，若各位数字递增，则删去最后一个数字；否则删去第一个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。重复以上过程s次为止，剩下的字串便是问题的解了。
【标程】
#include
}
for(k=j;k for(i=0;i for(j=i;j<=l-1;j++) cout< 【例3-2】取数游戏 【问题描述】 给出2n（n<=100）个自然数(数小于等于30000)。游戏双方分别为A方（计算机）和B方（对弈的人）。只允许从数列两头取数。A先取，然后双方一次轮流取数。取完时，谁取得的数字总和最大为取胜方；若双方和相同，属于A胜。试问A方可否有必胜的策略？ 输入：4 7 9 3 6 4 2 5 3 R R R R 键盘输入n以及2*n个自然数。 输出： 3 5 2 4 6 3 9 7 36 19 共3n+2行，其中前3*n行为游戏过程。每三行分别为A方所取的数和B方所取的数，及B方取数前应给与适当的提示，让游戏者选取那一头的数（L/R—左端或右端）。最后两行分别为A方取数之和与B方取数之和。 【标程】 program ho; var n,i,j,sa,sb,lp,rp,t:longint; ch:char; a:array[1..200]of longint; begin readln(n); for i:=1 to 2*n do read(a[i]); sa:=0; sb:=0; for i:=1 to n do begin sa:=sa+a[2*i-1]; sb:=sb+a[2*i]; end; if sa>=sb then j:=1 else begin j:=0; t:=sa; sa:=sb; sb:=t; end; lp:=1; rp:=2*n; for i:=1 to n do begin if (j=1)and(lp mod 2=1)or((j=0)and(lp mod 2=0)) then begin writeln(a[lp]); inc(lp); end else begin writeln(a[rp]); dec(rp); end; write('B=L/R?'); repeat readln(ch); if ch='L' then begin writeln(a[lp]); inc(lp); end; if ch='R' then begin writeln(a[rp]); dec(rp); end; until(ch='L')or(ch='R'); end; writeln(sa); writeln(sb); end. 【例3-3】活动选择 【问题描述】 假设有一个需要使用某以资源的n个活动组成的集合S，S={1,?，n}。该资源一次只能被一个活动占用，每一个活动有一个开始时间bi和结束时间ei（bi<=ei）。若bi>=ej或bj>=ei,则活动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