step5-算法设计技术

《step5-算法设计技术》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录算B06矩阵取数游戏（递归→动规）1算B07擦数游戏（贪心法）2算B08割钢管（分治法）3算B09数列找数（选择问题，快排）4算B10奖学金（多键排序）5算B11翻转排序6算B12埃及分数（贪心法）7算B13最少钱币数（贪心→动规）8算B14关宠物（串查找）9算B15平方数10注：算表示本题属于算法设计技术，B表示稍难。9算B06矩阵取数游戏（递归→动规）【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：1.每次取数时须从每行各取走一个元素，共n个

2、。m次后取完矩阵所有元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分=被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4.游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。【数据输入】输入有多个测试数据，每个包括n+1行：第1行为两个用空格隔开的整数n和m。第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。1<=n,m<=80,0<=aij<=1000【数据输出】对每个数

3、据，输出一行，为一个整数，即输入矩阵取数后的最大得分。相邻两个输出间用一个空行隔开。【样例输入】1445052109656544686122388804316951829305388836467【样例输出】1223169949算B07擦数游戏（贪心法）【问题描述】小W发明了一个游戏，他在黑板上写出了一行数字a1,a2,….an，然后给你m个回合的机会，每回合你可以从中选择一个数擦去它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合，所有你擦去的数字之和就是你所得到的分数。小W和他的好朋友小Y玩了这个游戏，可是他

4、发现，对于每个给出的an和bn序列，小Y的得分总是比他高，所以他就很不服气。于是他想让你帮他算算，对于每个an和bn序列，可以得到的最大得分是多少。这样他就知道有没有可能超过小Y的得分。【数据输入】第一行，一个整数n（1<=n<=200），表示数字的个数。第二行，一个整数m（1<=m<=n），表示回合数。接下来一行有n个不超过10000的正整数，a1,a2…an，表示原始数字，最后一行有n个不超过500的正整数，b1,b2….bn，表示每回合每个数字递减的值【数据输出】一个整数，表示最大可能的得分【样例输入】33102030

5、456【样例输出】479算B08割钢管（分治法）【问题描述】A公司有一台钢管切割机提供钢管加工业务。钢管切割机每次可以将一根钢管按照要求在指定位置切割为2段。每次切割的费用为钢管的长度。给定一根长度为L的钢管，要求将其在位置l1

6、.【样例输入】154391214【样例输出】339算B09数列找数（选择问题，快排）【问题描述】在一个数组A[N]存储N个互不相等的数，键盘输入正整数M(M≤N)，要求打印出数组中第M大的数。例如：数组A[10]的数据为：{16,57,20,19,38,41,6,13,25,32}，M=3时的运行结果为：A[4]=38（即第3大的数是38）。【数据输入】第一行为测试的数据的组数k，说明共有K组数据，每一组有两行。每组中第一行为N，M,第二行为N个下标变量的值。【数据输出】输出每一组数据中符合要求的下标值和下标变量值。【样例输

7、入】2516834532123【样例输出】829算B10奖学金（多键排序）【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。每个学生期末都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。【数据输入】输入包含多组测试数据，每个测试数据

8、有n+1行。第1行为一个正整数n，表示该校参加评选的学生人数。第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。所给的数据都是正确的