7-45 航空公司VIP客户查询(PTA算法中文集)

2023-11-23 00:11

本文主要是介绍7-45 航空公司VIP客户查询(PTA算法中文集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

7-45 航空公司VIP客户查询

分数 25

作者 DS课程组

单位 浙江大学

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

800
15000
1000
No Info

first:

         unordered_map:


#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>using namespace std;unordered_map<string,int> mp;int main()
{int n,t;scanf("%d%d",&n,&t);for(int i=0;i<n;++i){string id;int num;id.resize(18);scanf("%s%d",&id[0],&num);if(num < t)mp[id] += t;elsemp[id] += num;}int m;scanf("%d",&m);for(int i=0;i<m;++i){string id;id.resize(18);scanf("%s",&id[0]);if(mp[id] == 0)puts("No Info");elseprintf("%d\n",mp[id]);}return 0;
}

运行结果:

second:

        Tire树,字典树:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>using namespace std;const int maxn = 1e6;
int son[maxn][11],cnt[maxn];
int idx;int t;void insert(const char *id,int dis)
{int p = 0;for(int i=0;i<18;++i){int u;if(isalpha(id[i]))u = 10;elseu = id[i] - '0';if(son[p][u] == 0)son[p][u] = ++idx;p = son[p][u];}if(dis < t)cnt[p] += t;elsecnt[p] += dis;
}int query(const char *id)
{int p = 0;for(int i=0;i<18;++i){int u;if(isalpha(id[i]))u = 10;elseu = id[i] - '0';if(son[p][u] == 0)return 0;p = son[p][u];}return cnt[p];
}int main()
{int n;scanf("%d%d",&n,&t);char id[18];int dis;for(int i=0;i<n;++i){scanf("%s%d",id,&dis);insert(id,dis);}int m;scanf("%d",&m);for(int i=0;i<m;++i){scanf("%s",id);int res = query(id);if(res == 0)puts("No Info");elseprintf("%d\n",res);}return 0;}

运行结果:

 对比来看,还是unordered_map 更胜一筹!

字典树学习传送门:

835. Trie字符串统计,836。最大异或对,(Tire树,字典树)_疯疯癫癫才自由的博客-CSDN博客

这篇关于7-45 航空公司VIP客户查询(PTA算法中文集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/413922

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

SQL表间关联查询实例详解

《SQL表间关联查询实例详解》本文主要讲解SQL语句中常用的表间关联查询方式,包括:左连接(leftjoin)、右连接(rightjoin)、全连接(fulljoin)、内连接(innerjoin)、... 目录简介样例准备左外连接右外连接全外连接内连接交叉连接自然连接简介本文主要讲解SQL语句中常用的表

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

MySQL中的交叉连接、自然连接和内连接查询详解

《MySQL中的交叉连接、自然连接和内连接查询详解》:本文主要介绍MySQL中的交叉连接、自然连接和内连接查询,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、引入二、交php叉连接(cross join)三、自然连接(naturalandroid join)四

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n