1、排序的应用排序的应用队形排列队形排列(queue.cpp)queue.cpp)【问题描述】【问题描述】小小明所在的合唱队共有明所在的合唱队共有N N个人（个人（N N为奇数）。为了准备一次演出，老师开始为她们安排合为奇数）。为了准备一次演出，老师开始为她们安排合唱队形了。大家都知道，合唱队形通常是中间高两端低的。老师是这样安排他们的队形的：唱队形了。大家都知道，合唱队形通常是中间高两端低的。老师是这样安排他们的队形的：先让所有的同学按高个儿在前的顺序排成一队。然后，最高的那位同学单独站出来，这是合先让所有的同学按高个儿在前的顺序排成一队。然后，最高的那位同学单独站出来，这是合唱队形的中心，再让
2、第二位同学站在她的左手边，让第三位同学站在她的右手边，再依次向唱队形的中心，再让第二位同学站在她的左手边，让第三位同学站在她的右手边，再依次向两端安排其他人两端安排其他人。事先给定所有人的身高，请输出她们站成合唱队形之后的身高顺序。事先给定所有人的身高，请输出她们站成合唱队形之后的身高顺序。【输入文件】【输入文件】输入文件输入文件queue.inqueue.in有两行；有两行；第第1 1行是一个整数行是一个整数N N，表示合唱队的总人数，已知，表示合唱队的总人数，已知N N为奇数，且为奇数，且1 1N N5151；第第2 2行是行是N N个整数，表示以厘米为单位的所有人的身高。个整数，表示以厘
3、米为单位的所有人的身高。【输出文件】【输出文件】输出文件输出文件queue.outqueue.out有有1 1行；行；只有只有N N个整数，表示她们按老师的要求站成合唱队形之后的身高顺序。个整数，表示她们按老师的要求站成合唱队形之后的身高顺序。【输入样例【输入样例1 1】7 7154 160 157 162 159 152 163154 160 157 162 159 152 163【输出样例【输出样例1 1】152 157 160 163 162 159 154152 157 160 163 162 159 154默认是将数据默认是将数据从小到大进行排列从小到大进行排列sort(sort(a
4、,a+na,a+n););或者或者sort(a+1,a+n+1);sort(a+1,a+n+1);打包货物打包货物(goods.cpp)goods.cpp)【问题描述问题描述】物流物流公司要发送一批货物，发送之前要对货物进行包装，现在有公司要发送一批货物，发送之前要对货物进行包装，现在有 N N 种货物，发送第种货物，发送第i i种种货货物的价格是物的价格是 Price Pricei i。物流公司有个规定，如果把任意的。物流公司有个规定，如果把任意的3 3种货物放在一起打包，那么种货物放在一起打包，那么这这3 3种种货货物之中价格最低的那种货物可以不用给钱。那么，为了节约成本，应该如何打包，才
5、能用最少物之中价格最低的那种货物可以不用给钱。那么，为了节约成本，应该如何打包，才能用最少的钱把这的钱把这 N N 种货物打包好？注意：种货物打包好？注意：最多最多3 3种种货物一起打包，你不能尝试着货物一起打包，你不能尝试着把把4 4种种货物放在一起打货物放在一起打包包。【输入文件输入文件】输入文件名为输入文件名为 goods.in goods.in。第一行，一个整数第一行，一个整数 N N。1=N=200001=N=20000。接下来有接下来有N N行，第行，第i i行是一个整数，表示发送第行是一个整数，表示发送第i i种的价钱种的价钱 Price Pricei i。1=Price 1=P
6、ricei i=100000dcd;/;/返回从大到小的结果返回从大到小的结果 奖学金奖学金(scholar.cpp)scholar.cpp)【问题描述】【问题描述】某某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5 5名学生发奖学金。期末，每个学生都有名学生发奖学金。期末，每个学生都有3 3门课的成绩：语文、数学、英语。门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那
7、么规定学号小的同学排在排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面前面，这样，每个学生的排序是唯一确定的。，这样，每个学生的排序是唯一确定的。【输入格式】【输入格式】输入输入文件包含文件包含n+1n+1行行：第第1 1行为一个正整数行为一个正整数n n，表示该校参加评选的学生人数。，表示该校参加评选的学生人数。第第2 2到到n+1n+1行，每行有行，每行有3 3个用空格隔开的数字，每个数字都个用空格隔开的数字，每个数字都在在0 0到到100100之间。之间。第第j j行的行的3 3个数字依次表示学号为个数字依次表示学号为j-1j-1的学生的语文、数学、英语的成绩。的学生
8、的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为每个学生的学号按照输入顺序编号为l ln.n.【输出格式】【输出格式】共有共有5 5行，每行是两个用空格隔开的正整数，依次表示行，每行是两个用空格隔开的正整数，依次表示前前5 5名名学生的学号和学生的学号和总分。总分。【输入样例】6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 【输出样例】6 2654 2643 2582 2441 237【数据规模】50%的数据满足：各学生的总成绩各不相同；100%的数据满足：6n300。针对以上这种需要多重条件排序多重条件排序的情况，我们
9、会将sort()sort()函数和结构体函数和结构体一起使用，以达到多条件排序多条件排序的目的。结构体结构体？结构体是属于一种结构体是属于一种自定义的数据类型自定义的数据类型,它可以将不同的标准数据类型（例如整型，它可以将不同的标准数据类型（例如整型，实型，字符等）整合成为一种新的数据类实型，字符等）整合成为一种新的数据类型。型。定义定义结构体结构体 structstructstructstruct student student/定义名叫定义名叫studentstudent的结构体的结构体 intint yu,shu,ying,zong,xuehaoyu,shu,ying,zong,xueh
10、ao;/定义语文、数学、英语、总分、学号这些属性定义语文、数学、英语、总分、学号这些属性;/;/分号一定要有分号一定要有student student a500a500;/定义定义studentstudent类型的数组类型的数组for(for(i i=1;i=1;iaai i.yuyuaai i.shushuaai i.yingying;aai i.zongzong=a=ai i.yu+ayu+a i i.shu+ashu+a i i.yingying;aai i.xuehaoxuehao=i i;/结构体的输入方法结构体的输入方法bool bool cmpcmp()()student a ,
11、student bstudent a ,student b 先先按总分从高到低排序，如果两个同学总分相同，按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面成绩都相同，那么规定学号小的同学排在前面if(if(a.zonga.zong!=!=b.zongb.zong)return)return a.zonga.zong b.zongb.zong;if if(a.yu!=b.yu)return(a.yu!=b.yu)return a.yub.yu;a.yub.yu;ret
12、urn return a.xuehaoa.xuehao b.xuehaob.xuehao;拯救花园拯救花园(flowers.cpp)flowers.cpp)问题描述：问题描述：一天，晨晨发现自己的n（2n100）只兔子跑到自己的花园里面，它们在尽情的吃着她的宝贝花卉。晨晨看在眼里痛在心里，她现在只能把兔子逐个的抓回笼子里面。而送每只兔子回去的时间都不同，例如送第i只兔子回去需要ti(1ti100)单位时间，那么晨晨送第i只兔子来回共需要花费2*ti单位时间，另外每一只兔子单位时间的破坏力都不同，例如第i只兔子单位时间内破坏di(1di100)朵花。现在的问题是，晨晨如何安排送这n只兔子回笼子才
13、能使这些兔子的破坏最小。输入格式：输入格式：第一行：一个整数n(1n100)；接着有n行，每行两个空格分开的整数ti di,分别代表第i只兔子的送回去的时间，和单位时间破坏力。输出格式：输出格式：一行：一个整数，代表这些兔子破坏多少花卉。输入样例：输入样例：63 12 52 33 24 11 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朵花。分析？分析？1 1、选择兔子的依据是什么？、选择兔子的依据是什么？2 2、是否需要排序？、是否需要排序？3 3、如果要排序的话，比较函数如、如果要排序的话，比较函数如何写？何写？
