NOIP2003。删数游戏，

NOIP2003。删数游戏，

【问题分析】
对于这道试题，一般可以采用这样一种解题方式：因为要删除S个数字，可以一个一个的删，每一次删除的目的都是使剩下的数尽量小。那么在每一次删除时，应该选择那个数字？最大的数字还是最左的数字？例如5768，通过观察可以知道删除7这个数字可以使剩余的数最小。通过思考可以得出结论，每一次删除的数字应该是这个数字序列中降序子序列最左边的数字。具体可以这样操作，按高位到低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首数符，这样形成了一个新的数串。然后回到串首，重复上述规则，删下一数符…以此类推，直至删除S个数符为止。
例如：N=“8796542”，S=4删数过程如下：
N=“8 7 9 6 5 4 2” //最左边的递减序列是87，删除“8”
“7 9 6 5 4 2” //最左边的递减序列是96542，删除9
“7 6 5 4 2” //最左边的递减序列是76542，删除“7”
“6 5 4 2” //最左边的递减序列是6542，删除“6”
“5 4 2”
【程序代码】
program delete;
var i，j，k，s:integer;
N:string;
begin
readln(n);
readln(s);
while s>0 do begin
I:=1;
while (i Inc(i);
delete(n，I，1);
dec(s);
end;
while (length(n)>1 and (n[1]=‘0’) do
delete(n，1，1)；
writeln(n);
end.
【问题思考】
由题可知，贪心算法的实现需要思考两个基本的问题：如何建立和方法的正确性。
如何建立。怎样从一个规模较小的解推出规模较大的解呢？拿这个例题来说，从数串5768删除2位数的模拟过程中推广到240位的数串删数过程。
方法的正确性。确保贪心算法确实是有效是使用贪心算法的关键所在。确定贪心算法是有效的，那么解决该问题在时间复杂度还是在空间的使用方面与其他方法想比较显得更为优势。以例题为例，删数方法是首先按高位到低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首数符，这样形成了一个新的数串。这样获得的新数肯定是最小的新数。
对于上述例题，假如我们按照其他的删数过程是正确的，删除最左边的数或者每次删除最大的数。同样以5768为例。删除5得768，删除8得576，都不是最小的数值，假设不成立，证明这种方式是错误的，按照原先设定的方法所得到的解是最优解。
由上例可以获知，贪心的使用需要严格的证明，保证问题的严密性，贪心方法的使用还需结合其他算法的使用，例如：排序、模拟、搜素、枚举等等，但是一旦证明了贪心方法使用的正确性，程序的运行效率会大大提高。证明使用贪心方法的正确性依靠的是严密的数学头脑和以往的经验积累，假如不具备这些条件，使用该方法需要谨慎。