信息奥林匹克竞赛之贪心算法-共29页课件

1、武松打老虎问题描述：曾经因打虎而文明的武松在x年后接到了景阳冈动物园的求助信，信上说：最近我们动物园逃跑了几只老虎，请您把它们抓回来，thank you！武松接到信后立刻上了山。正当他到半山腰是，suddenly！跳出n只猛虎来。每只老虎都有一块虎牌，牌上写着的是每一只虎最大拥有的体力，当武松与老虎PK时，若老虎的体力先用完，那么老虎over，否则武松over。求武松在over之前最多能干掉几只老虎？（注：老虎是一只只上的）输入文件：第一行两个数字n(nb+a，就把a排在b的前面，反之则把a排在b的后面。如：12 123因为：1212312312所以：123在12之前如：12 121因为：12

2、11212121所以：12在121之前代码框架int cmp(char *s1,char *s2) 比较函数 int main()scanf(%d,&n); for(i=1;i 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10）。输入描述： 第一行N（N 堆纸牌，1 = N = 100） 第二行A1 A2 An （N 堆纸牌，每堆纸牌初始数，l= Ai =10000）输出描述：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。样例输入49 8 17 6样例输出：3分析设ai为第i堆纸牌的张数（0=i=n），v为均分后每堆纸牌的张数，s为最小移到

3、次数。按照从左到右的顺序移动纸牌。如第i堆(0iv，则将ai-v张纸牌从第I堆移动到第I+1堆；（2） 若aiv，则将v -ai张纸牌从第I+1堆移动到第I堆；为了设计的方便，我们把这两种情况统一看作是将aI-v张牌从第I堆移动到第I+1堆；移动后有：aI:=v；aI+1:=aI+1+aI-v；贪心选择：分析我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张纸牌，第二堆剩下-7张纸牌，再从第三堆移动17张到第二堆，刚好三堆纸牌数都是10，最后结果是对的，从第二堆移出的牌都可以从第三堆得到。我们在移动过程中，只是改变了移动的顺序，而移动的次数不变，因此此题使用贪心法是可行的。

4、在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(ai+1+ai-v0 )的情况。如n=3，三堆纸牌数为（1，2，27）这时v=10，为了使第一堆数为10，要从第二堆移9张纸牌到第一堆，而第二堆只有2张纸牌可移，这是不是意味着刚才使用的贪心法是错误的呢？当不具备贪心选择性质时：得到较优解。数字三角如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。贪心法：7+8+1+7+5=28更优方案：贪心法：更优方案：7+3+8+7+5=30策略：从第一层开始选，每次选择可选的数字中最大的数字第二层选择小些的数目能达到更优解不符合贪心选择性质分析当不能100%确定一个贪心算法正确时，在使用之前，就应该尝试证明它的不正确性。要证明其不正确，一种最简单的方法就