资源描述
单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2020/1/9,#,排序的应用,排序的应用,1,队形排列,(,queue.cpp),【问题描述】,小,明所在的合唱队共有,N,个人（,N,为奇数）。为了准备一次演出，老师开始为她们安排合唱队形了。大家都知道，合唱队形通常是中间高两端低的。老师是这样安排他们的队形的：先让所有的同学按高个儿在前的顺序排成一队。然后，最高的那位同学单独站出来，这是合唱队形的中心，再让第二位同学站在她的左手边，让第三位同学站在她的右手边，再依次向两端安排其他人。事先给定所有人的身高，请输出她们站成合唱队形之后的身高顺序。,【输入文件】,输入文件,queue.in,有两行；,第,1,行是一个整数,N,，表示合唱队的总人数，已知,N,为奇数，且,1,N,51,；,第,2,行是,N,个整数，表示以厘米为单位的所有人的身高。,【输出文件】,输出文件,queue.out,有,1,行；,只有,N,个整数，表示她们按老师的要求站成合唱队形之后的身高顺序。,【输入样例,1,】,7,154 160 157 162 159 152 163,【输出样例,1,】,152 157 160 163 162 159 154,队形排列(queue.cpp),2,默认是将数据,从小到大进行排列,sort(a,a+n);,或者,sort(a+1,a+n+1);,默认是将数据从小到大进行排列sort(a,a+n);或者,3,打包货物,(,goods.cpp),【,问题描述,】,物流,公司要发送一批货物，发送之前要对货物进行包装，现在有,N,种货物，发送第,i,种,货物的价格是,Pricei,。物流公司有个规定，如果把任意的,3,种货物放在一起打包，那么,这,3,种,货物之中价格最低的那种货物可以不用给钱。那么，为了节约成本，应该如何打包，才能用最少的钱把这,N,种货物打包好？注意：,最多,3,种,货物一起打包，你不能尝试着,把,4,种,货物放在一起打包,。,【,输入文件,】,输入文件名为,goods.in,。,第一行，一个整数,N,。,1=N=20000,。,接下来有,N,行，第,i,行是一个整数，表示发送第,i,种的价钱,Pricei,。,1=Priceid,;/,返回从大到小的结果,bool cmp(int c,int d)/比较函数,6,奖学金,(,scholar.cpp),【问题描述】,某,小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前,5,名学生发奖学金。期末，每个学生都有,3,门课的成绩：语文、数学、英语。,先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面,，这样，每个学生的排序是唯一确定的。,【输入格式】,输入,文件包含,n+1,行,：,第,1,行为一个正整数,n,，表示该校参加评选的学生人数。,第,2,到,n+1,行，每行有,3,个用空格隔开的数字，每个数字都,在,0,到,100,之间。第,j,行的,3,个数字依次表示学号为,j-1,的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为,l,n.,【输出格式】,共有,5,行，每行是两个用空格隔开的正整数，依次表示,前,5,名,学生的学号和总分。,奖学金(scholar.cpp),7,【输入样例】,6,90 67 80,87 66 91,78 89 91,88 99 77,67 89 64,78 89 98,【输出样例】,6 265,4 264,3 258,2 244,1 237,【数据规模】,50%,的数据满足：各学生的总成绩各不相同；,100%,的数据满足：,6,n,300,。,【输入样例】,8,针对以上这种需要,多重条件排序,的情况，我们会将,sort(),函数和结构体,一起使用，以达到,多条件排序,的目的,。,针对以上这种需要多重条件排序的情况，我们会将sort,9,结构体？,结构体是属于一种,自定义的数据类型,它可以将不同的标准数据类型（例如整型，实型，字符等）整合成为一种新的数据类型。,结构体？结构体是属于一种自定义的数据类型,它可以将,10,定义,结构体,struct,struct,student,/,定义名叫,student,的结构体,int,yu,shu,ying,zong,xuehao,;,/,定义语文、数学、英语、总分、学号这些属性,;/,分号一定要有,定义结构体 structstruct student/定,11,student,a500,;,/,定义,student,类型的数组,for(i=1;iai.yuai.shuai.ying;ai.zong=ai.yu+ai.shu+ai.ying;ai.xuehao=i;,/,结构体的输入方法,student a500;/定义student类型的数,12,bool cmp(),student a ,student b,先,按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面,if(a.zong!=b.zong)return a.zongb.zong;,if,(a.yu!=b.yu)return,a.yub.yu;,return a.xuehaob.xuehao;,bool cmp(,13,拯救花园,(,flowers.cpp),问题描述：,一天，晨晨发现自己的,n,（,2,n,100,）只兔子跑到自己的花园里面，它们在尽情的吃着她的宝贝花卉。晨晨看在眼里痛在心里，她现在只能把兔子逐个的抓回笼子里面。而送每只兔子回去的时间都不同，例如送第,i,只兔子回去需要,ti(1,ti,100),单位时间，那么晨晨送第,i,只兔子来回共需要花费,2*ti,单位时间，另外每一只兔子单位时间的破坏力都不同，例如第,i,只兔子单位时间内破坏,di(1,di,100),朵花。,现在的问题是，晨晨如何安排送这,n,只兔子回笼子才能使这些兔子的破坏最小。,输入格式：,第一行：一个整数,n(1,n,100),；,接着有,n,行，每行两个空格分开的整数,ti di,分别代表第,i,只兔子的送回去的时间，和单位时间破坏力。,输出格式：,一行：一个整数，代表这些兔子破坏多少花卉。,输入样例：,6,3 1,2 5,2 3,3 2,4 1,1 6,输出样例：,86,样例解释：,晨晨送兔子回去的顺序分别为：,6,2,3,4,1,5,。其中先送第,6,只兔子回去，剩余兔子破坏,(1+5+3+2+1)*2=24,朵花；送第,2,只兔子回去，剩余兔子破坏（,1+3+2+1,）,*4=28,朵花；以此类推，送第,3,、,4,、,1,只兔子回去剩余兔子的破坏分别为,16,、,12,和,6,朵花；最后送第,5,只兔子回去的时候，没有兔子在花园里面了，所以破坏,0,朵花，最后总共破坏,24+28+16+12+6=86,朵花。,拯救花园(flowers.cpp)样例解释：,14,分析？,1,、选择兔子的依据是什么？,2,、是否需要排序？,3,、如果要排序的话，比较函数如何写？,分析？1、选择兔子的依据是什么？,15,
展开阅读全文