此題如果一下子想到了思路確實是應(yīng)該很快出的，這題暴露了我基本功不扎實的弱點，對qsort中cmp函數(shù)和sort中cmp函數(shù)的使用沒有完全弄明白，通過這題終于搞明白了啊，初學(xué)者如果只是按網(wǎng)上的寫法套個模板還是遠(yuǎn)遠(yuǎn)不夠的，因為解決的問題是在不斷變化的，一定要深入研究其原理，才能遇神殺神，遇佛殺佛。
既然提到了這題，我說下兩個函數(shù)的不同之處吧，我覺得肯定有很多人不會，我記得很多人還跟我說這兩個函數(shù)的寫法是一樣的。。。。。至于qsort的cmp函數(shù)中要用const void * 這些我就不說了，直接切入主題，對qsort的cmp函數(shù)，返回值是int，這個函數(shù)要考慮<,=,>三種情況，而sort的cmp函數(shù)，返回值是bool ，也就是只有兩種情況，如果你用過sort進(jìn)行結(jié)構(gòu)體排序的話，你會發(fā)現(xiàn)其實你只要重載小于符號就可以進(jìn)行排序，其實這個cmp函數(shù)就等價于你重載了結(jié)構(gòu)體的<運(yùn)算符，明白了么？
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名得到的分?jǐn)?shù)
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;
}
基本功基本功^_^