此题如果一下子想到了思路确实是应该很快出的，这题暴露了我基本功不扎实的弱点，对qsort中cmp函数和sort中cmp函数的使用没有完全弄明白，通过这题终于搞明白了啊，初学者如果只是按网上的写法套个模板还是远远不够的，因为解决的问题是在不断变化的，一定要深入研究其原理，才能遇神杀神，遇佛杀佛。
既然提到了这题，我说下两个函数的不同之处吧，我觉得肯定有很多人不会，我记得很多人还跟我说这两个函数的写法是一样的。。。。。至于qsort的cmp函数中要用const void * 这些我就不说了，直接切入主题，对qsort的cmp函数，返回值是int，这个函数要考虑<,=,>三种情况，而sort的cmp函数，返回值是bool ，也就是只有两种情况，如果你用过sort进行结构体排序的话，你会发现其实你只要重载小于符号就可以进行排序，其实这个cmp函数就等价于你重载了结构体的<运算符，明白了么？
Sort版：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
map <string,int> mm;
map <int,string> mm2;
int points[10] = 
{ 25, 18, 15 , 12 , 10 , 8, 6 , 4, 2, 1 };
struct node
{
int a[1010];
int p;
int pos;
};
node per[2000];
int ca,n;
string s;
int id=0;
bool cmp1(node a, node b)
{
if (a.p != b.p)
return a.p > b.p;
for (int i = 0; i < id; i ++)
if (a.a[i] != b.a[i])
return a.a[i] > b.a[i];
return false;
}
bool cmp2(node a, node b)
{
if (a.a[0] != b.a[0])
return a.a[0] > b.a[0];
if (a.p != b.p)
return a.p > b.p;
for (int i = 1; i < id; i ++)
if (a.a[i] != b.a[i])
return a.a[i] > b.a[i];
return false;
}
int main()
{
cin >> ca;
mm.clear();
mm2.clear();
while(ca--)
{
cin >> n;
for (int i = 0; i < n; i ++)
{
cin >> s;
if (mm.find(s) == mm.end())
{
mm[s] = id;
mm2[id]=s;
per[id].pos=id;
per[id].p = 0;
id++;
}
per[mm[s]].a[i]++;
if (i < 10)
per[mm[s]].p += points[i];
}
}
sort(per, per + id, cmp1);
cout << mm2[per[0].pos]<< endl;
sort(per, per + id, cmp2);
cout << mm2[per[0].pos] << endl;
return 0;
}
Qsort版
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
int point[10]={25,18,15,12,10,8,6,4,2,1};//前10名得到的分数
map<string,int>mm;
map<int,string>mm2;
struct node
{
int p;
int a[2000];
int pos;
}per[2000];
int id=0;
int getid(string s)
{
if(mm.find(s)==mm.end())
{
mm[s]=id++;
mm2[id-1]=s;
return id-1;
}
else
return mm[s];
}
/**//*
bool cmp1(node a, node b)
{
if (a.p != b.p)
return a.p > b.p;
int i;
for (i = 0; i < 100; i ++)
if (a.a[i] != b.a[i])
return a.a[i] > b.a[i];
return false;
}
bool cmp2(node a,node b)
{
if(a.a[0]!=b.a[0])
return a.a[0]>b.a[0];
if(a.p!=b.p)
return a.p>b.p;
int i;
for(i=0;i<id;i++)
if(a.a[i]!=b.a[i])
return a.a[i]>b.a[i];
return false;
}
*/
int cmp1(const void *a,const void *b)
{
node *c=(node*)a;
node *d=(node*)b;
if(c->p!=d->p)
{
if(c->p > d->p)
return -1;
else
return 1;
}
int i;
for(i=0;i<id;i++)
{
if(c->a[i]>d->a[i])
return -1;
else if(c->a[i] < d->a[i])
return 1;
}
return 0;
}
int cmp2(const void *a,const void *b)
{
node *c=(node*)a;
node *d=(node*)b;
if(c->a[0]>d->a[0])
return -1;
else if(c->a[0] < d->a[0])
return 1;
if(c->p!=d->p)
{
if(c->p > d->p)
return -1;
else
return 1;
}
int i;
for(i=1;i<id;i++)
{
if(c->a[i]>d->a[i])
return -1;
else if(c->a[i] < d->a[i])
return 1;
}
return 0;
}
int main()
{
int ca;
scanf("%d",&ca);
mm.clear();
mm2.clear();
while(ca--)
{
int n;
scanf("%d",&n);
//cin.ignore();
string s;
int i;
for(i=0;i<n;i++)
{
cin>>s;
int k=getid(s);
if(i<10)
{
per[k].p+=point[i];
}
per[k].a[i]++;
per[k].pos=k;
}
}
qsort(per,id,sizeof(per[0]),cmp1);
cout<<mm2[per[0].pos]<<endl;
qsort(per,id,sizeof(per[0]),cmp2);
cout<<mm2[per[0].pos]<<endl;
return 0;
}
基本功基本功^_^