本文主要是介绍哈希算法--7-13 航空公司VIP客户查询 （25 分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
思路：
读完题目之后的第一思路就是用map将客户的id（string类型）与里程road（int类型）形成映射，然后直接用id查找添加里程或输出里程。但是400ms的限制妥妥的超时了。然后意识到要用哈希做，但是用哈希就有一点不好解决，每个客户的里程怎么保存，考虑了很长时间无果，搜了一下博客，发现可以用结构体来保存，平常用数组模拟链表的时候都是直接开的一维数组，所以当每个客户的信息多了后就没有结构体来的理解方便了。
第一次尝试：这个题N的上限是1e5，所以将每个客户的id转换成long long类型，然后对1e5+7取余，结果作为下标对应到数组里边存里程，完美过样例，提交果断WA。。。。。。。
第二次尝试：又看了一遍题目，思考了一下，哈希会出现冲突，需要处理冲突。所以数组模拟链表处理冲突，提交AC。
代码：
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#define INF 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)using namespace std;
typedef long long ll;
typedef pair<int,string> P;
const int maxn = 1e5+7;
int head[maxn];
struct Peo{char name[20];int road;int next;
}p[maxn];
int cnt = 0;int GetId(char* str) {ll res = 0;for(int i = 0; i<strlen(str); i++) {if(isdigit(str[i])) {res = res*10 + str[i]-'0';} else {res = res*10 + 10;}}return (int)(res%maxn);
}void Add_Node(char* str,int id,int temp){bool ok = true;for(int i = head[id]; ~i; i = p[i].next){if(strcmp(str,p[i].name) == 0){p[i].road += temp;ok = false;}}if(ok){int i = 0;p[cnt].road += temp;for(i = 0; str[i]; i++){p[cnt].name[i] = str[i];}p[cnt].name[i] = '\0';p[cnt].next = head[id];head[id] = cnt++;}return;
}bool ToFind(char* str,int id){for(int i = head[id]; i!=-1; i = p[i].next){if(strcmp(str, p[i].name) == 0){cout<<p[i].road<<endl;return true;}}return false;
}int main() {char str[20];int n,k,temp;cin>>n>>k;memset(head,-1,sizeof(head));for(int i = 0; i<n; i++) {cin>>str>>temp;if(temp<k) temp = k;int index = GetId(str);Add_Node(str,index,temp);}int m;cin>>m;for(int i = 0; i<m; i++) {cin>>str;int index = GetId(str);if(!ToFind(str,index)){printf("No Info\n");}}return 0;
}
这篇关于哈希算法--7-13 航空公司VIP客户查询 （25 分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
