数据结构与算法题目集（中文） - 7-14 电话聊天狂人（25 分）_7-1 电话聊天狂人 分数 25 作者 ds课程组 单位 浙江大学 给定大量手机用户通话记

题目链接：点击打开链接

题目大意：略。

解题思路：hash，自定义hash规则 + 结构体数组 + 结构体中的每个链表。

AC 代码

#include<bits/stdc++.h>
#include<cmath>
 
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
 
using namespace std;
 
typedef long long ll;
 
const int maxn=1e5+100;
 
ll mi_tel,ma_Cnt;
int mergeCnt;
 
struct node
{
    ll tel;
    int cnt;
    node *next;
}nds[maxn];
 
void init()
{
    ma_Cnt=0;
    mergeCnt=1;
    mi_tel=LLONG_MAX;
 
    for(int i=0;i<maxn;i++)
    {
        nds[i].tel=-1;
        nds[i].cnt=0;
        nds[i].next=NULL;
    }
}
 
node * findTel(ll tel)
{
    node * nd;
    // 自定义hash规则
    // TEL：130 0571 1862
    // -> tel[9] + tel[10] + tel[7] + tel[1] + tel[2]
    // -> 62130
    int idx=0;
    idx+=tel%100;
    idx=idx*10+tel/10000%10;
    idx=idx*100+tel/100000000%100;
//    cout<<"idx = "<<idx<<endl;
 
    nd=&nds[idx];
    if(nd->tel==-1)
    {
        nd->tel=tel;
        return nd;
    }
 
    while(nd->tel!=tel)
    {
        if(nd->next==NULL)
        {
            nd->next=(node*)malloc(sizeof(node));
            nd=nd->next;
            nd->next=NULL;
            nd->tel=tel;
            nd->cnt=0;
            break;
        }
        else
            nd=nd->next;
    }
 
    return nd;
}
 
void insert(ll tel)
{
    node * nd=findTel(tel);
    nd->cnt++;
    if(nd->cnt>ma_Cnt)
    {
        ma_Cnt++;
        mergeCnt=1;
        mi_tel=tel;
    }
    else if(nd->cnt==ma_Cnt)
    {
        mergeCnt++;
        if(tel<mi_tel) mi_tel=tel;
    }
}
 
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        init();
        ll tel1,tel2;
        for(int i=0;i<n;i++)
        {
            scanf("%lld%lld",&tel1,&tel2);
            insert(tel1);
            insert(tel2);
        }
 
        printf("%lld %d",mi_tel,ma_Cnt);
        if(mergeCnt>1) printf(" %d",mergeCnt);
        puts("");
    }
 
    return 0;
}