1092 最好吃的月饼 (20分) 月饼是久负盛名的中国传统糕点之一，自唐朝以来，已经发展出几百品种 若想评比出一种“最好吃”的月饼，那势必在吃货界引发一场腥风血雨…… 在这里我们用数字说话，给出全国各地各种月饼的销量，要求你从中找出销量冠军，认定为最好吃的月饼。 输入格式: 输入首先给出两个正整数 N（≤1000）和 M（≤100），分别为月饼的种类数（于是默认月饼种类从 1 到 N 编号）和参与统计的城市数量。
接下来 M 行，每行给出 N 个非负整数（均不超过 1 百万），其中第 i 个整数为第 i 种月饼的销量（块）。数字间以空格分隔 输出格式 在第一行中输出最大销量，第二行输出销量最大的月饼的种类编号。如果冠军不唯一，则按编号递增顺序输出并列冠军。数字间以 1 个空格分隔，行首尾不得有多余空格。 输入样例：
5 3 1001 992 0 233 6 8 0 2018 0 2008 36 18 0 1024 4
输出样例：
2018 3 5
思路 题目要求输出月饼销量的最大值，和最大值的序号。我的思路是建立结构体保存月饼的序号和销量，然后调用c++内置的sort函数，自己写一个比较函数，这是pat乙级惯用的套路，乙级题中很多排序都是这种套路，文章末尾会讲一下这种思路。这种写法便于理解，适合我这种弱鸡。
struct yuebing{ int id; int num; }cake[1000]; bool cmp(yuebing a,yuebing b) { if(a.num!=b.num) return a.num>b.num;//先按照数量递减排序 else return a.id<b.id;//如果数量相等的话，按照编号递增排序 //这意味排序时 数量 的优先级高于 序号 }另外说一下，今天在写代码时发现sort函数不能对map排序，如果要对map排序，可以将map的两个值写在一个结构体里，然后插入到vector中，这样就间接完成了对map的排序，在后续1095题中我会写到。
我的代码
#include<algorithm> using namespace std; const int M=110;//注意数据范围 const int N=1000; struct yuebing{ int id; int num; }cake[1000]; bool cmp(yuebing a,yuebing b) { if(a.num!=b.num) return a.num>b.num; else return a.id<b.id; } int main() { int n,m; cin>>n>>m; int a[M][N],i,j; for(i=0;i<m;i++) { for(j=0;j<n;j++) { scanf("%d",&a[i][j]); } } for(j=0;j<n;j++) { for(i=0;i<m;i++) { cake[j].num+=a[i][j];//记录每种月饼的数量 cake[j].id=j+1; //记录月饼的编号，从1开始，所以要加一 } } sort(cake,cake+n,cmp);//排序 printf("%d\n%d",cake[0].num,cake[0].id); for(int i=1;i<n;i++) { if(cake[i].num!=cake[0].num) break; else {printf(" ");printf("%d",cake[i].id);} } return 0; }顾名思义，sort()是用来排序的函数，推荐在算法题中写，这样的好处是忽略了具体排序的细节，只关心结果，节省写代码的时间，毕竟排序在算法题中只占很少的一部分，把时间留给其他部分是很重要的。
如何使用sort排序 首先，必须加上头文件 #include< algorithm >和using namespace std; sort(首元素地址(必填),尾元素的下一个地址(必填),比较函数(非必填));比较函数不是必填的，如果不填的话是对数据默认递增排序；
如何实现比较函数cmp 如果对序列进行排序，那么序列中的元素一定是具有可比性的。那么有对结构体怎么排序呢？这个时候需要我们自己编写cmp函数。 如下，编写cmp函数，实现递减排序
#include<iostream> #include<algorithm> using namespace std; bool cmp(int a,int b){ return a>b;//a大于b时为真，也就是递减 } int main() { int a[]={3,1,4,2}; sort(a,a+4,cmp); for(auto i:a) cout<<i<<" "; return 0; }结构体数组的排序
struct node{ int x; int y; }n[10];我们如果想按照x的递减顺序对结构体数组n排序，cmp函数如下
bool cmp(node a,node b)//对两个结构体对象进行比较 { return a.x>b.x;//按照x递减顺序排序 } #include<iostream> #include<algorithm> using namespace std; struct node{ int x; int y; }n[10]; bool cmp(node a,node b)//对两个结构体对象进行比较 { return a.x>b.x;//按照x递减顺序排序 } int main() { n[0].x=2; n[0].y=4; n[1].x=1; n[1].y=5; n[2].x=3; n[2].y=4; sort(n,n+3,cmp); for(int i=0;i<3;i++) cout<<n[i].x<<" "<<n[i].y<<endl; return 0; }输出结果： 3 4 2 4 1 5
如果想先按照x从大到小排序，但x相等的情况下，按照y递增排序，cmp可以改写如下：
bool cmp(node a,node b)//对两个结构体对象进行比较 { if(a.x!=b.x) return a.x>b.x;//x递减 else return a.y<b.y;//x相同时，y递增 }示例如下：
#include<iostream> #include<algorithm> using namespace std; struct node{ int x; int y; }n[10]; bool cmp(node a,node b)//对两个结构体对象进行比较 { if(a.x!=b.x) return a.x>b.x;//x递减 else return a.y<b.y;//x相同时，y递增 } int main() { n[0].x=2; n[0].y=4; n[1].x=2; n[1].y=5; n[2].x=3; n[2].y=4; sort(n,n+3,cmp); for(int i=0;i<3;i++) cout<<n[i].x<<" "<<n[i].y<<endl; return 0; }输出结果： 3 4 2 4 2 5
是不是很简单呢？
容器的排序 在STL中，可以用sort的容器有vector，string，deque。set和map是不能直接用sort的，因为这种容器用红黑树实现的（不会的当我没说，哈哈，记住就好，别用错），本身就是有顺序的。关于sort函数目前我能说的就这么多，本人能力有限，如有大佬肯指正，万分感谢。在pat乙级和csp认证的简单题中，使用sort可以很快的得到答案，尤其是在结构体的二级排序中。你想想 ，在别人还在手写冒泡时，你已经交上了正确的答案，是不是美滋滋呢，嘿嘿。
