The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Codeforces Beta Round #24 B题

      此题如果一下子想到了思路确实是应该很快出的,这题暴露了我基本功不扎实的弱点,对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= 251815 , 12 , 10 , 86 , 421 }

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->> 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->> 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;
}


基本功基本功^_^

posted on 2010-07-29 11:41 abilitytao 阅读(1393) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理