首页 > 代码库 > 5-45 航空公司VIP客户查询 (25分)

5-45 航空公司VIP客户查询 (25分)

不少航空公司都会提供优惠的会员服务,当某顾客飞行里程累积达到一定数量后,可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录,要求实现根据身份证号码快速查询会员里程积分的功能。

输入格式:

输入首先给出两个正整数NN(\le 10^510?5??)和KK(\le 500500)。其中KK是最低里程,即为照顾乘坐短程航班的会员,航空公司还会将航程低于KK公里的航班也按KK公里累积。随后NN行,每行给出一条飞行记录。飞行记录的输入格式为:18位身份证号码(空格)飞行里程。其中身份证号码由17位数字加最后一位校验码组成,校验码的取值范围为0~9和x共11个符号;飞行里程单位为公里,是(0, 15 000]区间内的整数。然后给出一个正整数MM(\le 10^510?5??),随后给出MM行查询人的身份证号码。

输出格式:

对每个查询人,给出其当前的里程累积值。如果该人不是会员,则输出No Info。每个查询结果占一行。

输入样例:

4 500
330106199010080419 499
110108198403100012 15000
120104195510156021 800
330106199010080419 1
4
120104195510156021
110108198403100012
330106199010080419
33010619901008041x

输出样例:

800
15000
1000
No Info
注意hash函数的选取,一开始我选取了后四位果断超时,选取了后五位即可AC,尽量让Hash函数取值接近数据最大值,这样能减少很多冲突。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN 10005
typedef long long LL;
/*
hash表
*/

typedef struct node
{
    char id[20];
    LL miles;
    struct node* next;
}*List;
typedef struct tb
{
    LL Tablesize;
    List *list;
}*Hashlist;
LL Hash(char key[],LL size)
{
    LL tmp = 0;
    for(LL i=13;i<18;i++)
    {
        if(key[i]==x)
            tmp = (tmp*10+10)%size;
        else
            tmp = (tmp*10 + key[i]-0)%size;
    }
    return tmp;
}
LL NextPrim(LL x)
{
    LL j;
    for(LL i=x;;i++)
    {
        for(j=2;j*j<=i;j++)
            if(i%j==0)
                break;
        if(j*j>i)
            return i;
    }
}
Hashlist Init(LL size)
{
    Hashlist H = (Hashlist)malloc(sizeof(tb));
    H->Tablesize = NextPrim(size);
    H->list = (List*)malloc(sizeof(List)*H->Tablesize);
    for(LL i=0;i<H->Tablesize;i++)
    {
        H->list[i] = (List)malloc(sizeof(node));
        H->list[i]->next = NULL;
    }
    return H;
}
List Find(char key[],Hashlist H)
{
    List t = H->list[Hash(key,H->Tablesize)];
    List p = t->next;
    while(p!=NULL && strcmp(key,p->id))
        p = p->next;
    return p;
}
void Insert(char key[],LL miles,Hashlist H)
{
    List t = H->list[Hash(key,H->Tablesize)];
    List f = Find(key,H);
    if(f==NULL)
    {
        List tmp = (List)malloc(sizeof(node));
        tmp->miles = miles;
        strcpy(tmp->id,key);
        tmp->next = t->next;
        t->next = tmp;
    }
    else
    {
        (f->miles) += miles;
    }
}

int main()
{
    char id[20];
    LL tmp,n,m,k;
    scanf("%lld%lld",&n,&k);
    Hashlist H = Init(n);
    for(LL i=0;i<n;i++)
    {
        scanf("%s%lld",id,&tmp);
        if(tmp<k) tmp = k;
        Insert(id,tmp,H);
    }
    scanf("%lld",&m);
    for(LL j=0;j<m;j++)
    {
        scanf("%s",id);
        List f = Find(id,H);
        if(f==NULL)
            printf("No Info\n");
        else
            printf("%lld\n",f->miles);
    }
}

 



5-45 航空公司VIP客户查询 (25分)