信息学c++排序的应用课件

排序的应用排序的应用1队形排列(queue.cpp)【问题描述】

小明所在的合唱队共有N个人（N为奇数）。为了准备一次演出，老师开始为她们安排合唱队形了。大家都知道，合唱队形通常是中间高两端低的。老师是这样安排他们的队形的：先让所有的同学按高个儿在前的顺序排成一队。然后，最高的那位同学单独站出来，这是合唱队形的中心，再让第二位同学站在她的左手边，让第三位同学站在她的右手边，再依次向两端安排其他人……。事先给定所有人的身高，请输出她们站成合唱队形之后的身高顺序。【输入文件】输入文件queue.in有两行；第1行是一个整数N，表示合唱队的总人数，已知N为奇数，且1≤N≤51；第2行是N个整数，表示以厘米为单位的所有人的身高。【输出文件】输出文件queue.out有1行；只有N个整数，表示她们按老师的要求站成合唱队形之后的身高顺序。【输入样例1】7154160157162159152163【输出样例1】152157160163162159154队形排列(queue.cpp)2默认是将数据从小到大进行排列sort(a,a+n);

或者

sort(a+1,a+n+1);默认是将数据从小到大进行排列sort(a,a+n);

或者

3打包货物(goods.cpp)【问题描述】

物流公司要发送一批货物，发送之前要对货物进行包装，现在有N种货物，发送第i种货物的价格是Price[i]。物流公司有个规定，如果把任意的3种货物放在一起打包，那么这3种货物之中价格最低的那种货物可以不用给钱。那么，为了节约成本，应该如何打包，才能用最少的钱把这N种货物打包好？注意：最多3种货物一起打包，你不能尝试着把4种货物放在一起打包。

【输入文件】输入文件名为goods.in。第一行，一个整数N。1<=N<=20000。接下来有N行，第i行是一个整数，表示发送第i种的价钱Price[i]。1<=Price[i]<=100000。【输出文件】输出文件名为goods.out。一个整数，最少的钱。输入样例good.in输出样例good.out样例解释432328可以把前3种货物打包，这样第2种货物不用给钱664555521分两次打包，可以省下9元打包货物(goods.cpp)输入样例good.in输出样4sort(a+1,a+n+1,cmp);cmp是一个比较函数,函数中定义了排序的条件返回值是bool型sort(a+1,a+n+1,cmp);cmp是一个比较函数5boolcmp(intc,intd)

//比较函数

{

returnc>d;//返回从大到小的结果

}boolcmp(intc,intd)//比较函数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 906780 876691 788991 889977 678964788998

【输出样例】62654264325822441237【数据规模】

50%的数据满足：各学生的总成绩各不相同；100%的数据满足：6≤n≤300。【输入样例】8

针对以上这种需要多重条件排序的情况，我们会将sort()函数和结构体一起使用，以达到多条件排序的目的。针对以上这种需要多重条件排序的情况，我们会将sort9结构体？

结构体是属于一种自定义的数据类型,它可以将不同的标准数据类型（例如整型，实型，字符等）整合成为一种新的数据类型。结构体？结构体是属于一种自定义的数据类型,它可以将10定义结构体structstructstudent//定义名叫student的结构体{intyu,shu,ying,zong,xuehao;//定义语文、数学、英语、总分、学号这些属性};//分号一定要有定义结构体structstructstudent//定11studenta[500];//定义student类型的数组for(i=1;i<=n;i++)

{

cin>>a[i].yu>>a[i].shu>>a[i].ying;

a[i].zong=a[i].yu+a[i].shu+a[i].ying;

a[i].xuehao=i;

}//结构体的输入方法studenta[500];//定义student类型的数12boolcmp()studenta,studentb{}

先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面if(a.zong!=b.zong)returna.zong>b.zong;if(a.yu!=b.yu)returna.yu>b.yu;returna.xuehao<b.xuehao;boolcmp(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行，每行两个空格分开的整数tidi,分别代表第i只兔子的送回去的时间，和单位时间破坏力。输出格式：一行：一个整数，代表这些兔子破坏多少花卉。输入样例：6312523324116输出样例：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排序的应用排序的应用16队形排列(queue.cpp)【问题描述】

小明所在的合唱队共有N个人（N为奇数）。为了准备一次演出，老师开始为她们安排合唱队形了。大家都知道，合唱队形通常是中间高两端低的。老师是这样安排他们的队形的：先让所有的同学按高个儿在前的顺序排成一队。然后，最高的那位同学单独站出来，这是合唱队形的中心，再让第二位同学站在她的左手边，让第三位同学站在她的右手边，再依次向两端安排其他人……。事先给定所有人的身高，请输出她们站成合唱队形之后的身高顺序。【输入文件】输入文件queue.in有两行；第1行是一个整数N，表示合唱队的总人数，已知N为奇数，且1≤N≤51；第2行是N个整数，表示以厘米为单位的所有人的身高。【输出文件】输出文件queue.out有1行；只有N个整数，表示她们按老师的要求站成合唱队形之后的身高顺序。【输入样例1】7154160157162159152163【输出样例1】152157160163162159154队形排列(queue.cpp)17默认是将数据从小到大进行排列sort(a,a+n);

或者

sort(a+1,a+n+1);默认是将数据从小到大进行排列sort(a,a+n);

或者

18打包货物(goods.cpp)【问题描述】

物流公司要发送一批货物，发送之前要对货物进行包装，现在有N种货物，发送第i种货物的价格是Price[i]。物流公司有个规定，如果把任意的3种货物放在一起打包，那么这3种货物之中价格最低的那种货物可以不用给钱。那么，为了节约成本，应该如何打包，才能用最少的钱把这N种货物打包好？注意：最多3种货物一起打包，你不能尝试着把4种货物放在一起打包。

【输入文件】输入文件名为goods.in。第一行，一个整数N。1<=N<=20000。接下来有N行，第i行是一个整数，表示发送第i种的价钱Price[i]。1<=Price[i]<=100000。【输出文件】输出文件名为goods.out。一个整数，最少的钱。输入样例good.in输出样例good.out样例解释432328可以把前3种货物打包，这样第2种货物不用给钱664555521分两次打包，可以省下9元打包货物(goods.cpp)输入样例good.in输出样19sort(a+1,a+n+1,cmp);cmp是一个比较函数,函数中定义了排序的条件返回值是bool型sort(a+1,a+n+1,cmp);cmp是一个比较函数20boolcmp(intc,intd)

//比较函数

{

returnc>d;//返回从大到小的结果

}boolcmp(intc,intd)//比较函数21奖学金(scholar.cpp)【问题描述】

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。【输入格式】输入文件包含n+1行：第1行为一个正整数n，表示该校参加评选的学生人数。第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为l～n.【输出格式】共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。奖学金(scholar.cpp)22【输入样例】6 906780 876691 788991 889977 678964788998

【输出样例】62654264325822441237【数据规模】

50%的数据满足：各学生的总成绩各不相同；100%的数据满足：6≤n≤300。【输入样例】23

针对以上这种需要多重条件排序的情况，我们会将sort()函数和结构体一起使用，以达到多条件排序的目的。针对以上这种需要多重条件排序的情况，我们会将sort24结构体？

结构体是属于一种自定义的数据类型,它可以将不同的标准数据类型（例如整型，实型，字符等）整合成为一种新的数据类型。结构体？结构体是属于一种自定义的数据类型,它可以将25定义结构体structstructstudent//定义名叫student的结构体{intyu,shu,ying,zong,xuehao;//定义语文、数学、英语、总分、学号这些属性};//分号一定要有定义结构体structstructstudent//定26studenta[500];//定义student类型的数组for(i=1;i<=n;i++)

{

cin>>a[i].yu>>a[i].shu>>a[i].ying;

a[i].zong=a[i].yu+a[i].shu+a[i].ying;

a[i].xuehao=i;

}//结构体的输入方法studenta[500];//定义student类型的数27boolcmp()studenta,studentb{}

先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面if(a.zong!=b.zong)returna.zong>b.zong;if(a.yu!=b.yu)returna.yu>b.yu;returna.xuehao<b.xuehao;boolcmp(28拯救花园(flowers.cpp)问题描述：一天，晨晨发现自己的n（2≤n≤100）只兔子跑到自己的花园里面，它们在尽