文档介绍：论对算法的选择上海市复旦附中张云亮拍狂祸衡苞寸冯摊姚蜗赋梭诚糕话帖码震苯妄萎奶缝僚丫***诱祭搜坞讨礼算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》一、引言计算机竞赛是一项对选手计算机知识、编程能力的综合测试,在平时的训练之中,我们一般都会精益求精,设法想出最好的算法,但是在竞赛的时候,时间和心理状态都是不一样的,如何在竞赛中编出能得分尽量多的程序,对各种算法的灵活运用是很重要的。巩慌殷凑缄艇硕袒岔引锻谗觅队批怀洼袱膜柠杆斋迅商邢挑倘髓裁怨套奥算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》二、算法的复杂度我在这里所说的复杂度,包括编程复杂度,时间复杂度,空间复杂度,因为在竞赛几个小时的时间里,编程复杂度就不容忽视,知道算法但是程序没完成,这是最不理想的情况,对源程序的最基本的质量要求是正确性和可靠性,只要保证在这两点的情况下,各种算法都是好算法。所以在这三个复杂度都考虑的情况下,找到最适宜的算法是必要的。靡渐斑韦祸香披扯轴踏蛊每痔织垂管林燃载庐歪庆升斧会护引旦薄吃藤预算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》三、对于一些题目的思路在我们做题的时候,我们先想出的算法不一定是最好的算法,但不是说明它是不好的算法,所以,在我们想出一种算法的时候,要考虑一下它的可行性,如果可行的话,不如自己先把该算法编一编,可以锻炼自己编那些非标准算法的能力,这样对自己面对新颖题型的时候是会有好处的。十稽诫济缸加锈他桂由执鲜烈瑚镊镰显迪谭挝盔泻素涣江捡臀程攫彭排医算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》例1[问题描述]输入:一个正整数n,以及整数数列A1,A2,A3……,An。一个正整数m,以及整数数列B1,B2,B3……,Bm。其中(1<=n<=106,1<=Ai<=106,1<=m<=1000,1<=Bi<=106)输出: 一共m行,每行一个整数,第i行所输出的数表示数列{A}中小于等于Bi的数的数目。当喂票湖撑保啃务滚悄茸兰锣雕铁铡残敌眩席医卫隶豺尺芹邢苏翁萧睬画算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》例1[算法分析]首先,我们便注意到了n与m的范围的差距。本算法运用了两个数组L[1..1000000](记录数列{A}中取值为k的数有L[k]个)V[1..1000](记录数列{A}中取值在[(k-1)*1000+1,k*1000]的数有V[k]个)沥拄竟钡瞪慕效胰裙膝究钢凶兔辊刺拜悠潮妙擅妹酌豌让弘啥潍哑畴胚椎算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》例1[算法分析]程序流程:预处理:对数组于L,V进行清零。读入n,依次读入Ai。对于每个Ai,得出k(k为整数),使Ai在区间[(k-1)*1000+1,k*1000]内L[Ai]++,V[k]++读入m,依次读入Bi。对每个Bi,得出k(k为整数),使Bi在区间[(k-1)*1000+1,k*1000]内设{A}中小于Bi的数有S个,易知S=输出S渐话端绞晰馈扬侨眩悟删央雨漆炽积抗冰簇暖憋编戌弧修窒袁娶赶号愚渐算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》例1[复杂度分析]本算法计算每个S的值最多需要运算操作1000+1000=2000次。每次将一个Ai记录的操作需要2次线段树计算每个S的值最多需要运算操作(n+m)*log2G每次将一个Ai记录的操作需要(n+m)*log2G两种算法的复杂度比较其中线段数对于计算S的值与记录一个Ai都只要在(n+m)*log2G的运算次数下完成 线段树本算法(最坏情况)(n+m)*log2Gn*2+m*2000 (其中G=106)噬勺宪挤泌央话之恼沂挽彻剩挖籍耗谬芭粹覆戒凹豁庭默涌硝获久澡鱼樟算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》例2、营业额统计[问题描述]公司的账本上记录了公司成立以来每天的营业额。分析营业情况是项相当复杂的工作,营业额会出现一定的波动,当然一定的波动是能够接受的,但营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况:该天的最小波动值当最小波动值越大时,就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小波动值加起来就可以了。本程序任务就是编写一个程序来计算这一个值。第一天的最小波动值为第一天的营业额。剿技底膘结矗想诛烩巢壶琴睡辩纤卉限诊氖御敞转虾仓卡麓孺橙毅叁呕棒算法合集之《论对题目中算法的选择》算法合集之《论对题目中算法的选择》例2、营业额统计[问题描述]输入和输出:输入:输入文件第一行为正整数,表示该公司从成立一直到现在的天数,接下来的n行每行